Symmetry and Dominance Breaking for Pseudo-Boolean Optimization

Daimy Stefanie Van Caudenberg, Bart Bogaerts

Research output: Chapter in Book/Report/Conference proceedingConference paper

75 Downloads (Pure)

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 languageEnglish
Title of host publicationArtificial Intelligence and Machine Learning
EditorsToon Calders, Vens Celine, Jefrey Lijffijt, Bart Goethals
Publisher Springer Nature Switzerland AG
Pages149-166
Number of pages18
ISBN (Electronic)978-3-031-39144-6
ISBN (Print)978-3-031-39144-6
DOIs
Publication statusPublished - 2023
EventBNAIC/BeNeLearn 2022: Joint International Scientific Conferences on AI and Machine Learning - Lamot Mechelen, Belgium
Duration: 7 Nov 20229 Nov 2022
https://bnaic2022.uantwerpen.be/

Publication series

NameCommunications in Computer and Information Science
Volume1805 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

ConferenceBNAIC/BeNeLearn 2022
Abbreviated titleBNAIC/BeNeLearn 2022
Country/TerritoryBelgium
CityLamot Mechelen
Period7/11/229/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.

Fingerprint

Dive into the research topics of 'Symmetry and Dominance Breaking for Pseudo-Boolean Optimization'. Together they form a unique fingerprint.

Cite this