Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs

Jasper van Doornmalen () and Christopher Hojny ()
Additional contact information
Jasper van Doornmalen: Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands
Christopher Hojny: Eindhoven University of Technology, 5612 AZ Eindhoven, Netherlands

INFORMS Journal on Computing, 2024, vol. 36, issue 3, 868-883

Abstract: 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.

Keywords: symmetry handling; cyclic group; propagation; branch-and-bound (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0060 (application/pdf)

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:inm:orijoc:v:36:y:2024:i:3:p:868-883

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().