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.