Breaking structured symmetries and sub-symmetries in Integer Linear Programming - Sorbonne Université
Conference Papers Year : 2019

Breaking structured symmetries and sub-symmetries in Integer Linear Programming

Cécile Rottner
  • Function : Author
  • PersonId : 1089275
Pascale Bendotti
Pierre Fouilhoux

Abstract

We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. Such structured subsymmetry groups arise in important classes of combinatorial problems, e.g. graph coloring or unit commitment. For a priori known (sub-)symmetries, we propose a framework to build (sub-)symmetry-breaking inequalities for such problems, by introducing one additional variable per considered sub-symmetry group. The derived inequalities are full-symmetry-breaking and in polynomial number w.r.t. the number of sub-symmetry groups considered. The proposed framework is applied to derive such inequalities when the symmetry group is the symmetric group acting on the columns. It is also applied to derive sub-symmetry-breaking inequalities for the graph coloring problem. Experimental results give insight into how to select the right inequality subset in order to efficiently break sub-symmetries. Finally, the framework is applied to derive (sub-)symmetry breaking inequalities for Min-up/min-down Unit Commitment Problem with or without ramp constraints. We show the effectiveness of the approach by presenting an experimental comparison with state-of-the-art symmetry-breaking formulations.
Fichier principal
Vignette du fichier
ROADEF2019.pdf (327.74 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03118582 , version 1 (22-01-2021)

Identifiers

  • HAL Id : hal-03118582 , version 1

Cite

Cécile Rottner, Pascale Bendotti, Pierre Fouilhoux. Breaking structured symmetries and sub-symmetries in Integer Linear Programming. ROADEF 2019 - 20ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision, Feb 2019, Le Havre, France. ⟨hal-03118582⟩
78 View
77 Download

Share

More