|Title||Exploiting symmetries within constraint satisfaction search|
|Publication Type||Journal Article|
|Year of Publication||2001|
|Authors||Meseguer P, Torras C|
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.
- About IIIA
- Current news