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