TítolExploiting symmetries within constraint satisfaction search
Publication TypeJournal Article
Year of Publication2001
AuthorsMeseguer P, Torras C
JournalArtificial Intelligence
Volume129
Número1-2
Paginació133-163
Resum

Symmetry often appears in real-world constraint satisfactionproblems, but strategies for exploiting it are only beginningto be developed. Here, a framework for exploiting symmetrywithin depth-first search is proposed, leading to two heuristicsfor variable selection and a domain pruning procedure. Thesestrategies are then applied to two highly symmetric combinatorialproblems, namely the Ramsey problem and the generation of balancedincomplete block designs. Experimental results show that thesegeneral-purpose strategies can compete with, and in some casesoutperform, previous more ad hoc procedures.