Symmetry Breaking in MILP Formulations for Unit Commitment Problems

by R. Lima, A. Novais
Refereed Journals Year: 2016

Bibliography

R. Lima, A. Novais, Symmetry Breaking in MILP Formulations for Unit Commitment Problems, Computers & Chemical Engineering, 85, p. 162-176., 2016

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. Symmetry issues are present in benchmark problems, and real world problems as it has been reported in the literature. In this work three sets of symmetry breaking constraints are proposed 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 models 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 clear advantage over the methods in the MILP solvers.

ISSN:

2016

Keywords

OR in Energy Unit Commitment MILP Symmetry Breaking