Conference Proceedings

Breaking symmetries with lex implications

M Codish, T Ehlers, G Gange, A Itzhakov, PJ Stuckey, John P Gallagher, M Sulzmann

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Springer | Published : 2018


© 2018, Springer International Publishing AG, part of Springer Nature. Breaking symmetries is crucial when solving hard combinatorial problems. A common way to eliminate symmetries in CP/SAT is to add symmetry breaking constraints. Ideally, symmetry breaking constraints should be complete and compact. The aim of this paper is to find compact and complete symmetry breaks applicable when solving hard combinatorial problems using CP/SAT approach. In particular: graph search problems and matrix model problems where symmetry breaks are often specified in terms of lex constraints. We show that sets of lex constraints can be expressed with only a small portion of their inner lex implications which ..

View full abstract


Awarded by Israel Science Foundation

Awarded by German Federal Ministry of Education and Research

Funding Acknowledgements

Supported by the Israel Science Foundation, grant 625/17 and the German Federal Ministry of Education and Research, combined project 01IH15006A.