Symmetry and Dominance Breaking for Pseudo-Boolean Optimization

Daimy Stefanie Van Caudenberg; Bart Bogaerts

doi:10.1007/978-3-031-39144-6_10

Symmetry and Dominance Breaking for Pseudo-Boolean Optimization

Daimy Stefanie Van Caudenberg, Bart Bogaerts

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

2 Citations (Scopus)

108 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 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	https://doi.org/10.1007/978-3-031-39144-6_10
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	https://bnaic2022.uantwerpen.be/

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.

Access to Document

10.1007/978-3-031-39144-6_10

PB-SymmetryDominanceAccepted author manuscript, 639 KB

Handle.net

Persistent link

Cite this

Van Caudenberg, D. S., & Bogaerts, B. (2023). Symmetry and Dominance Breaking for Pseudo-Boolean Optimization. In T. Calders, V. Celine, J. Lijffijt, & B. Goethals (Eds.), Artificial Intelligence and Machine Learning (pp. 149-166). (Communications in Computer and Information Science; Vol. 1805 CCIS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-39144-6_10

@inproceedings{42898cb1cf8e4616879fc25c9e033c07,

title = "Symmetry and Dominance Breaking for Pseudo-Boolean Optimization",

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.",

author = "{Van Caudenberg}, {Daimy Stefanie} and Bart Bogaerts",

note = "Funding Information: Acknowledgement. This project had received funding from the European Research Council (ERC) under the European Union{\textquoteright}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: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; BNAIC/BeNeLearn 2022 : Joint International Scientific Conferences on AI and Machine Learning, BNAIC/BeNeLearn 2022 ; Conference date: 07-11-2022 Through 09-11-2022",

year = "2023",

doi = "10.1007/978-3-031-39144-6_10",

language = "English",

isbn = "978-3-031-39144-6",

series = "Communications in Computer and Information Science",

publisher = " Springer Nature Switzerland AG",

pages = "149--166",

editor = "Toon Calders and Vens Celine and Jefrey Lijffijt and Bart Goethals",

booktitle = "Artificial Intelligence and Machine Learning",

url = "https://bnaic2022.uantwerpen.be/",

}

Van Caudenberg, DS & Bogaerts, B 2023, Symmetry and Dominance Breaking for Pseudo-Boolean Optimization. in T Calders, V Celine, J Lijffijt & B Goethals (eds), Artificial Intelligence and Machine Learning. Communications in Computer and Information Science, vol. 1805 CCIS, Springer Nature Switzerland AG, pp. 149-166, BNAIC/BeNeLearn 2022, Lamot Mechelen, Belgium, 7/11/22. https://doi.org/10.1007/978-3-031-39144-6_10

Symmetry and Dominance Breaking for Pseudo-Boolean Optimization. / Van Caudenberg, Daimy Stefanie; Bogaerts, Bart.
Artificial Intelligence and Machine Learning. ed. / Toon Calders; Vens Celine; Jefrey Lijffijt; Bart Goethals. Springer Nature Switzerland AG, 2023. p. 149-166 (Communications in Computer and Information Science; Vol. 1805 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - GEN

T1 - Symmetry and Dominance Breaking for Pseudo-Boolean Optimization

AU - Van Caudenberg, Daimy Stefanie

AU - Bogaerts, Bart

N1 - 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.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85172124513&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-39144-6_10

DO - 10.1007/978-3-031-39144-6_10

M3 - Conference paper

SN - 978-3-031-39144-6

T3 - Communications in Computer and Information Science

SP - 149

EP - 166

BT - Artificial Intelligence and Machine Learning

A2 - Calders, Toon

A2 - Celine, Vens

A2 - Lijffijt, Jefrey

A2 - Goethals, Bart

PB - Springer Nature Switzerland AG

T2 - BNAIC/BeNeLearn 2022

Y2 - 7 November 2022 through 9 November 2022

ER -