Exploiting symmetries in mathematical programming via orbital independence

Gustavo Dias () and Leo Liberti ()
Additional contact information
Gustavo Dias: CNRS LIX, École Polytechnique
Leo Liberti: CNRS LIX, École Polytechnique

Annals of Operations Research, 2021, vol. 298, issue 1, No 9, 149-182

Abstract: Abstract 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 them 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, might make all of the global optima infeasible. In this paper we introduce and test a new concept of Orbital Independence designed to address this issue. 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 identifies the largest independent set of orbits of any mathematical program. Extensive numerical experiments are provided to validate the theoretical results.

Keywords: Combinatorial optimization; Symmetry breaking; Group theory; Quadratic programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03145-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:298:y:2021:i:1:d:10.1007_s10479-019-03145-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03145-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().