Symmetry Breaking via LexLeader Feasibility Checkers
Abstract
This paper considers matrix models, a class of CSPs which generally exhibit significant symmetries. It proposed the idea of LexLeader feasibility checkers that verify, during search, whether the current partial assignment can be extended into a canonical solution. The feasibility checkers are based on a novel result by [Katsirelos et al., 2010] on how to check efficiently whether a solution is canonical. The paper generalizes this result to partial assignments, various variable orderings, and value symmetries. Empirical results on 5 standard benchmarks shows that feasibility checkers may bring significant performance gains, when jointly used with DoubleLex or SnakeLex.
Cite
Text
Yip and Van Hentenryck. "Symmetry Breaking via LexLeader Feasibility Checkers." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-121Markdown
[Yip and Van Hentenryck. "Symmetry Breaking via LexLeader Feasibility Checkers." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/yip2011ijcai-symmetry/) doi:10.5591/978-1-57735-516-8/IJCAI11-121BibTeX
@inproceedings{yip2011ijcai-symmetry,
title = {{Symmetry Breaking via LexLeader Feasibility Checkers}},
author = {Yip, Justin and Van Hentenryck, Pascal},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {687-692},
doi = {10.5591/978-1-57735-516-8/IJCAI11-121},
url = {https://mlanthology.org/ijcai/2011/yip2011ijcai-symmetry/}
}