Solving Strategies for Highly Symmetric CSPs
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 400-404.
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 procedur e. These strategies are then applied to a highly symmetric comb inat orial 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. Int erestingly, two previously developed strategies are shown to be particular instances of this approach.
@inproceedings{ijcai1999p58,
title = {Solving Strategies for Highly Symmetric CSPs},
author = {Meseguer, Pedro and Torras, Carme},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {400--404},
year = {1999},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1999/58},
}
TY - CPAPER TI - Solving Strategies for Highly Symmetric CSPs AU - Meseguer, Pedro AU - Torras, Carme T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 400 EP - 404 UR - https://ijcai.org/proceedings/1999/58 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
