Symmetry and Dominance Breaking for Pseudo-Boolean Optimization

Daimy Stefanie Van Caudenberg, Bart Bogaerts

Onderzoeksoutput: Conference paper

48 Downloads (Pure)

Samenvatting

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.

Originele taal-2English
TitelArtificial Intelligence and Machine Learning
RedacteurenToon Calders, Vens Celine, Jefrey Lijffijt, Bart Goethals
Uitgeverij Springer Nature Switzerland AG
Pagina's149-166
Aantal pagina's18
ISBN van elektronische versie978-3-031-39144-6
ISBN van geprinte versie978-3-031-39144-6
DOI's
StatusPublished - 2023
EvenementBNAIC/BeNeLearn 2022: Joint International Scientific Conferences on AI and Machine Learning - Lamot Mechelen, Belgium
Duur: 7 nov 20229 nov 2022
https://bnaic2022.uantwerpen.be/

Publicatie series

NaamCommunications in Computer and Information Science
Volume1805 CCIS
ISSN van geprinte versie1865-0929
ISSN van elektronische versie1865-0937

Conference

ConferenceBNAIC/BeNeLearn 2022
Verkorte titelBNAIC/BeNeLearn 2022
Land/RegioBelgium
StadLamot Mechelen
Periode7/11/229/11/22
Internet adres

Bibliografische nota

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Vingerafdruk

Duik in de onderzoeksthema's van 'Symmetry and Dominance Breaking for Pseudo-Boolean Optimization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit