DoubleLex Revisited and Beyond
Other conference paper


Full Text

Other information
AbstractThe 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.
Acceptance Date10/05/2019
All Author(s) ListXuming Huang, Jimmy Lee
Name of ConferenceThe 28th International Joint Conference on Artificial Intelligence
Start Date of Conference10/08/2019
End Date of Conference16/08/2019
Place of ConferenceMacao, China
Country/Region of ConferenceMacau
Proceedings TitleProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Year2019
Month8
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1101 - 1107
eISBN978-0-9992411-4-1
LanguagesEnglish-United States
KeywordsConstraint Satisfaction, Formulation, Symmetry Breaking

Last updated on 2020-24-11 at 15:20