19/03/2025    15:00 > "Structured-symmetry-breaking techniques in Integer Linear Programming, case study on the Unit Commitment Problem". 

Cécile Rottner (EDF) 

will give a presentation on : 

Structured-symmetry-breaking techniques in Integer Linear Programming, case study on the Unit Commitment Problem. 

Abstract : 

Symmetries arising in integer linear programs (ILP) can impair the solution process, in particular when symmetric solutions lead to an excessively large Branch and Bound search tree. Various techniques, so called symmetry-breaking techniques, are available to handle symmetries in ILP. A symmetry is defined as a permutation of the variables such that for any solution, the image of the permutation is also solution, with same cost. The symmetry group is the set of all such permutations. In this presentation, we focus on structured symmetries, defined when symmetry groups contain all sub-column permutations of given solution submatrices. These symmetry groups are assumed to be known or previously detected. Such general symmetry structure arise in various combinatorial problem structures (bin packing, graph coloring, etc) and is present in particular in the Unit Commitment Problem (UCP), when some production units are identical. We review and classify methods to handle structured symmetries in ILP, and propose a numerical analysis of the performance on various UCP instances.

   CORE B.-135