Solving Strategies for Highly Symmetric CSPs
Abstract
Symmetry often appears in real-world constraint satisfaction problems, but strategies for exploiting it are only beginning to be developed. Here, a rationale for exploiting symmetry within depth-first search is proposed, leading to an heuristic for variable selection and a domain pruning procedure. These strategies are then applied to a highly symmetric combinatorial problem, namely the generation of balanced incomplete block designs. Experimental results show that these strategies achieve a reduction of up to two orders of magnitude in computational effort. Interestingly, two previously developed strategies are shown to be particular instances of this approach.
Cite
Text
Meseguer and Torras. "Solving Strategies for Highly Symmetric CSPs." International Joint Conference on Artificial Intelligence, 1999.Markdown
[Meseguer and Torras. "Solving Strategies for Highly Symmetric CSPs." International Joint Conference on Artificial Intelligence, 1999.](https://mlanthology.org/ijcai/1999/meseguer1999ijcai-solving/)BibTeX
@inproceedings{meseguer1999ijcai-solving,
title = {{Solving Strategies for Highly Symmetric CSPs}},
author = {Meseguer, Pedro and Torras, Carme},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1999},
pages = {400-405},
url = {https://mlanthology.org/ijcai/1999/meseguer1999ijcai-solving/}
}