Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs
Ist Teil von
INFORMS journal on computing, 2024-05, Vol.36 (3), p.868-883
Ort / Verlag
INFORMS
Erscheinungsjahr
2024
Quelle
美国运筹学和管理学研究协会期刊(NSTL购买)
Beschreibungen/Notizen
The presence of symmetries in binary programs typically degrades the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from symmetry arguments; that is, one cannot find more variable fixings than those found by our algorithms. Because every permutation symmetry group of a binary program has cyclic subgroups, the derived algorithms can be used to handle symmetries in any symmetric binary program. In experiments, we also provide numerical evidence that our algorithms handle symmetries more efficiently than other variable fixing algorithms for cyclic symmetries.
History:
Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete.
Supplemental Material:
The online appendix is available at
https://doi.org/10.1287/ijoc.2022.0060
.