Symmetry Breaking via LexLeader Feasibility Checkers
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 687-691.
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.
@inproceedings{ijcai2011p121,
title = {Symmetry Breaking via LexLeader Feasibility Checkers},
author = {Yip, Justin and Van Hentenryck, Pascal},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {687--691},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-121},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-121},
}
TY - CPAPER TI - Symmetry Breaking via LexLeader Feasibility Checkers AU - Yip, Justin AU - Van Hentenryck, Pascal T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 687 EP - 691 DO - 10.5591/978-1-57735-516-8/IJCAI11-121 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-121 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
