Abstract
It is well-known that highly symmetric problems can often be challenging for combinatorial search and optimization solvers. One technique to avoid this problem is to introduce so-called symmetry breaking constraints, which eliminate some symmetric parts of the search space. In this paper, we focus on pseudo-Boolean optimization problems, which are specified by a set of 0–1 integer linear inequalities (also known as pseudo-Boolean constraints) and a linear objective. Symmetry breaking has already been studied in this context; however previous work could only deal with symmetries of the entire optimization problem. In this paper, we show how to handle weak symmetries: symmetries of the constraints that do not necessarily need to respect the objective. We show that weak symmetries induce a dominance relation and that pseudo-Boolean constraints are a natural target formalism to write the dominance breaking constraints in. We implemented these ideas on top of a state-of-the-art symmetry breaking tool for SAT, and in doing so also transfer modern symmetry breaking techniques to pseudo-Boolean optimization. We experimentally validate our approach on the latest pseudo-Boolean competition, as well as on hard combinatorial instances and conclude that the effect of breaking (weak) symmetries depends greatly on the type of solving algorithm used.
Original language | English |
---|---|
Title of host publication | Artificial Intelligence and Machine Learning |
Editors | Toon Calders, Vens Celine, Jefrey Lijffijt, Bart Goethals |
Publisher | Springer Nature Switzerland AG |
Pages | 149-166 |
Number of pages | 18 |
ISBN (Electronic) | 978-3-031-39144-6 |
ISBN (Print) | 978-3-031-39144-6 |
DOIs | |
Publication status | Published - 2023 |
Event | BNAIC/BeNeLearn 2022: Joint International Scientific Conferences on AI and Machine Learning - Lamot Mechelen, Belgium Duration: 7 Nov 2022 → 9 Nov 2022 https://bnaic2022.uantwerpen.be/ |
Publication series
Name | Communications in Computer and Information Science |
---|---|
Volume | 1805 CCIS |
ISSN (Print) | 1865-0929 |
ISSN (Electronic) | 1865-0937 |
Conference
Conference | BNAIC/BeNeLearn 2022 |
---|---|
Abbreviated title | BNAIC/BeNeLearn 2022 |
Country/Territory | Belgium |
City | Lamot Mechelen |
Period | 7/11/22 → 9/11/22 |
Internet address |
Bibliographical note
Funding Information:Acknowledgement. This project had received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 758824—INFLUENCE).
Funding Information:
This work was partially supported by Fonds Wetenschappelijk Onderzoek – Vlaanderen (FWO) (project G070521N); computational resources and services were provided by the VSC (Flemish Supercomputer Center), funded by FWO and the Flemish Government.
Funding Information:
Acknowledgement. We thank the reviewers for their constructive input, which helped improve the paper. This work was jointly supported by the Flanders Innovation & Entrepreneurship (VLAIO project HBC.2019.2467), Research Foundation - Flanders under EOS No. 30992574, and the Flemish Government (AI Research Program). We want to thank Tunify for providing us with their data and guidance throughout this project.
Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.