Symmetries and Lazy Clause Generation

Chu, Geoffrey; Stuckey, Peter J.; de la Banda, Maria Garcia; Mears, Christopher

doi:10.5591/978-1-57735-516-8/IJCAI11-094

Symmetries and Lazy Clause Generation

Geoffrey Chu, Peter J. Stuckey, Maria Garcia de la Banda, Christopher Mears

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 516-520.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-094

Abstract

Lazy clause generation is a powerful approach to reducing search in constraint programming. This is achieved by recording sets of domain restrictions that previously led to failure as new clausal propagators. Symmetry breaking approaches are also powerful methods for reducing search by recog- nizing that parts of the search tree are symmetric and do not need to be explored. In this paper we show how we can successfully combine symmetry breaking methods with lazy clause generation. Further, we show that the more precise nogoods generated by a lazy clause solver allow our combined approach to exploit redundancies that cannot be exploited via any previous symmetry breaking method, be it static or dynamic.

Geoffrey Chu, Peter J. Stuckey, Maria Garcia de la Banda, and Christopher Mears. 2011. Symmetries and Lazy Clause Generation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 516–520. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-094

@inproceedings{ijcai2011p94,
  title     = {Symmetries and Lazy Clause Generation},
  author    = {Chu, Geoffrey and Stuckey, Peter J. and de la Banda, Maria Garcia and Mears, Christopher},
  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     = {516--520},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-094},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-094},
}

TY  - CPAPER
TI  - Symmetries and Lazy Clause Generation
AU  - Chu, Geoffrey
AU  - Stuckey, Peter J.
AU  - de la Banda, Maria Garcia
AU  - Mears, Christopher
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  - 516
EP  - 520
DO  - 10.5591/978-1-57735-516-8/IJCAI11-094
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-094
ER  -