Symmetry Breaking in MILP Formulations for Unit Commitment Problems

Ricardo Lima; Augusto Q. Novais

doi:10.1016/j.compchemeng.2015.11.004

Symmetry Breaking in MILP Formulations for Unit Commitment Problems

Ricardo Lima, Augusto Q. Novais

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

This paper addresses the study of symmetry in Unit Commitment (UC) problems solved by Mixed Integer Linear Programming (MILP) formulations, and using Linear Programming based Branch & Bound MILP solvers. We propose three sets of symmetry breaking constraints for UC MILP formulations exhibiting symmetry, and its impact on three UC MILP models are studied. The case studies involve the solution of 24 instances by three widely used models in the literature, with and without symmetry breaking constraints. The results show that problems that could not be solved to optimality within hours can be solved with a relatively small computational burden if the symmetry breaking constraints are assumed. The proposed symmetry breaking constraints are also compared with the symmetry breaking methods included in two MILP solvers, and the symmetry breaking constraints derived in this work have a distinct advantage over the methods in the MILP solvers.

Original language	English (US)
Pages (from-to)	162-176
Number of pages	15
Journal	Computers & Chemical Engineering
Volume	85
DOIs	https://doi.org/10.1016/j.compchemeng.2015.11.004
State	Published - Dec 16 2015

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

General Chemical Engineering
Computer Science Applications

Access to Document

10.1016/j.compchemeng.2015.11.004

https://repository.kaust.edu.sa/bitstream/10754/584028/1/1-s2.0-S0098135415003622-main.pdf

Cite this

@article{20b889d4810d41fabf96a4a196abac92,

title = "Symmetry Breaking in MILP Formulations for Unit Commitment Problems",

abstract = "This paper addresses the study of symmetry in Unit Commitment (UC) problems solved by Mixed Integer Linear Programming (MILP) formulations, and using Linear Programming based Branch & Bound MILP solvers. We propose three sets of symmetry breaking constraints for UC MILP formulations exhibiting symmetry, and its impact on three UC MILP models are studied. The case studies involve the solution of 24 instances by three widely used models in the literature, with and without symmetry breaking constraints. The results show that problems that could not be solved to optimality within hours can be solved with a relatively small computational burden if the symmetry breaking constraints are assumed. The proposed symmetry breaking constraints are also compared with the symmetry breaking methods included in two MILP solvers, and the symmetry breaking constraints derived in this work have a distinct advantage over the methods in the MILP solvers.",

author = "Ricardo Lima and Novais, {Augusto Q.}",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2015",

month = dec,

day = "16",

doi = "10.1016/j.compchemeng.2015.11.004",

language = "English (US)",

volume = "85",

pages = "162--176",

journal = "Computers & Chemical Engineering",

issn = "0098-1354",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Symmetry Breaking in MILP Formulations for Unit Commitment Problems

AU - Lima, Ricardo

AU - Novais, Augusto Q.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2015/12/16

Y1 - 2015/12/16

N2 - This paper addresses the study of symmetry in Unit Commitment (UC) problems solved by Mixed Integer Linear Programming (MILP) formulations, and using Linear Programming based Branch & Bound MILP solvers. We propose three sets of symmetry breaking constraints for UC MILP formulations exhibiting symmetry, and its impact on three UC MILP models are studied. The case studies involve the solution of 24 instances by three widely used models in the literature, with and without symmetry breaking constraints. The results show that problems that could not be solved to optimality within hours can be solved with a relatively small computational burden if the symmetry breaking constraints are assumed. The proposed symmetry breaking constraints are also compared with the symmetry breaking methods included in two MILP solvers, and the symmetry breaking constraints derived in this work have a distinct advantage over the methods in the MILP solvers.

AB - This paper addresses the study of symmetry in Unit Commitment (UC) problems solved by Mixed Integer Linear Programming (MILP) formulations, and using Linear Programming based Branch & Bound MILP solvers. We propose three sets of symmetry breaking constraints for UC MILP formulations exhibiting symmetry, and its impact on three UC MILP models are studied. The case studies involve the solution of 24 instances by three widely used models in the literature, with and without symmetry breaking constraints. The results show that problems that could not be solved to optimality within hours can be solved with a relatively small computational burden if the symmetry breaking constraints are assumed. The proposed symmetry breaking constraints are also compared with the symmetry breaking methods included in two MILP solvers, and the symmetry breaking constraints derived in this work have a distinct advantage over the methods in the MILP solvers.

UR - http://hdl.handle.net/10754/584028

UR - http://linkinghub.elsevier.com/retrieve/pii/S0098135415003622

UR - http://www.scopus.com/inward/record.url?scp=84951964012&partnerID=8YFLogxK

U2 - 10.1016/j.compchemeng.2015.11.004

DO - 10.1016/j.compchemeng.2015.11.004

M3 - Article

SN - 0098-1354

VL - 85

SP - 162

EP - 176

JO - Computers & Chemical Engineering

JF - Computers & Chemical Engineering

ER -

Symmetry Breaking in MILP Formulations for Unit Commitment Problems

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this