Faster Certified Symmetry Breaking Using Orders With Auxiliary Variables
Created by
Haebom
저자
Markus Anders, Bart Bogaerts, Benjamin Bog{\o}, Arthur Gontier, Wietze Koops, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordstrom, Andy Oertel, Adrian Rebola-Pardo, Yong Kiam Tan
개요
본 논문은 조합 문제 해결에서 중요한 기법인 대칭성 파괴의 올바른 구현을 보장하는 방법을 제시한다. 특히, 해를 출력할 뿐만 아니라 표준 형식의 정확성 증명을 제공하는 인증 솔버를 구축하는 데 초점을 맞춘다. 기존의 대칭성 추론을 증명에 포함시키는 효율적인 방법을 개발하는 것은 오랜 과제였으며, 본 연구에서는 보조 변수를 사용하여 순서를 인코딩하는 새로운 방법을 제안한다. 이를 통해 대규모 대칭성에 적합하고, 기존 방법보다 훨씬 빠른 속도를 낼 수 있다. SAT 대칭성 파괴에 대한 실험을 통해 성능 향상을 입증한다.