Publication
Exploiting symmetries within constraint satisfaction search
Journal Article (2001)
Journal
Artificial Intelligence
Pages
133-163
Volume
129
Number
1
Doc link
http://dx.doi.org/10.1016/S0004-3702(01)00104-7
File
Abstract
Symmetry often appears in real-world constraint satisfaction problems, but strategies for exploiting it are only beginning to be developed. Here, a framework for exploiting symmetry within depth-first search is proposed, leading to two heuristics for variable selection and a domain pruning procedure. These strategies are then applied to two highly symmetric combinatorial problems, namely the Ramsey problem and the generation of balanced incomplete block designs. Experimental results show that these general-purpose strategies can compete with, and in some cases outperform, previous more ad hoc procedures.
Categories
robots.
Author keywords
symmetry, constraint satisfaction, heuristics, nogoods
Scientific reference
P. Meseguer and C. Torras. Exploiting symmetries within constraint satisfaction search. Artificial Intelligence, 129(1): 133-163, 2001.
Follow us!