EUVIMEDEUVIMED entdecken
Crossref

Faster Certified Symmetry Breaking Using Orders with Auxiliary Variables

Markus Anders, Bart Bogaerts, Benjamin Bogø, Arthur Gontier, Wietze Koops, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Adrian Rebola-Pardo, Yong Kiam Tan

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14140-14148

DOI: 10.1609/aaai.v40i17.38426 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Markus Anders und 10 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Symmetry breaking is a crucial technique in modern combinatorial solving, but it is difficult to be sure it is implemented correctly. The most successful approach to deal with bugs is to make solvers certifying, so that they output not just a solution, but also a mathematical proof of correctness in a standard format, which can then be checked by a formally verified checker. This requires justifying symmetry reasoning within the proof, but developing efficient methods for this has remained a long-standing open challenge. A fully general approach was recently proposed, but it relies on encoding lexicographic orders with big integers, which quickly becomes infeasible for large symmetries. In this work, we develop a method for instead encoding orders with auxiliary variables. We show that this leads to orders-of-magnitude speed-ups in both theory and practice by running experiments on proof logging and checking for SAT symmetry breaking using the state-of-the-art satsuma symmetry breaker and the VeriPB proof checking toolchain.

Zitieren

APA

Anders, M., Bogaerts, B., Bogø, B., Gontier, A., Koops, W., McCreesh, C., Myreen, M. O., Nordström, J., Oertel, A., Rebola-Pardo, A., & Tan, Y. K. (2026). Faster Certified Symmetry Breaking Using Orders with Auxiliary Variables. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14140-14148. https://doi.org/10.1609/aaai.v40i17.38426

Vancouver

Anders M, Bogaerts B, Bogø B, Gontier A, Koops W, McCreesh C, et al. Faster Certified Symmetry Breaking Using Orders with Auxiliary Variables. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14140-14148. doi:10.1609/aaai.v40i17.38426

BibTeX
@article{Anders2026,
  author = {Anders, Markus and Bogaerts, Bart and Bogø, Benjamin and Gontier, Arthur and Koops, Wietze and McCreesh, Ciaran and Myreen, Magnus O. and Nordström, Jakob and Oertel, Andy and Rebola-Pardo, Adrian and Tan, Yong Kiam},
  title = {Faster Certified Symmetry Breaking Using Orders with Auxiliary Variables},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {17},
  pages = {14140--14148},
  doi = {10.1609/aaai.v40i17.38426}
}
Kostenlos starten →