Exploiting symmetries in mathematical programming via orbital independence

Gustavo Dias , Leo Liberti (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

The presence of symmetries in the solution set of mathematical programs requires the exploration of symmetric subtrees during the execution of Branch-and-Bound type algorithms and yields increases in computation times. When some of the solution symmetries are evident in the formulation, it is possible to deal with symmetries as a preprocessing step. In this sense, implementation-wise, one of the simplest approaches is to break symmetries by adjoining Symmetry-Breaking Constraints (SBCs) to the formulation. Designed to remove some of the symmetric global optima, these constraints are generated from each orbit of the action of the symmetries on the variable index set. Incompatible SBCs however make all of the global optima infeasible. In this paper we introduce and test a new concept of Orbital Independence which we define as independent sets of orbits. We provide necessary conditions for characterizing independent sets of orbits and also prove that such sets embed sufficient conditions to exploit symmetries from two or more distinct orbits concurrently. The theory developed is used to devise an algorithm that potentially identifies the largest independent set of orbits of any mathematical program. Extensive numerical experiments are provided to validate the theoretical results.

Domaines: Recherche opérationnelle [math.OC]

Gustavo Dias, Leo Liberti. Exploiting symmetries in mathematical programming via orbital independence. Annals of Operations Research, inPress, ⟨10.1007/s10479-019-03145-x⟩. ⟨hal-02869231⟩