DoubleLex Revisited and Beyond

DoubleLex Revisited and Beyond

Xuming Huang, Jimmy Lee

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1101-1107. https://doi.org/10.24963/ijcai.2019/154

The paper proposes Maximum Residue (MR) as a notion to evaluate the strength of a symmetry breaking method. We give a proof to improve the best known DoubleLex MR upper bound from m!n! - (m!+n!) to min(m!,n!) for an m x n matrix model. Our result implies that DoubleLex works well on matrix models where min(m, n) is relatively small. We further study the MR bounds of SwapNext and SwapAny, which are extensions to DoubleLex breaking further a small number of composition symmetries. Such theoretical comparisons suggest general principles on selecting Lex-based symmetry breaking methods based on the dimensions of the matrix models. Our experiments confirm the theoretical predictions as well as efficiency of these methods.
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Modeling;Formulation