@InProceedings{10.1007/978-3-031-39144-6_10,
author="Van Caudenberg, Daimy
and Bogaerts, Bart",
editor="Calders, Toon
and Vens, Celine
and Lijffijt, Jefrey
and Goethals, Bart",
title="Symmetry and Dominance Breaking for Pseudo-Boolean Optimization",
booktitle="Artificial Intelligence and Machine Learning",
year="2023",
publisher="Springer Nature Switzerland",
address="Cham",
pages="149--166",
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.",
isbn="978-3-031-39144-6"
}