Symmetry maps solutions to solutions and nonsolutions to nonsolutions. Many constraint programming problems are highly symmetric. Symmetry in constraint programs can cause problems for an algorithm that searches a space of partial assignments, due to redundancy in the search space. Reformulation, adding constraints before search, and adding constraints during search are some ways to break symmetry.

In the social golfer problem, g groups of s golfers play golf for w weeks, such that any two golfers in the same group play at most once. This paper proposes a variation of symmetry breaking via dominance detection (SBDD) that does deep pruning when a symmetry is detected during search, supporting the computation of all of the nonsymmetric solutions for small instances of the social golfer problem.

Barnier and Brisset provide a good introduction to the problem, the best solutions so far for all three approaches, and a good presentation of their variation of SBDD, SBDD+. Their algorithm is based on their observation that most of the symmetries found between two complete solutions involve a mapping from the first week onto itself. Deep pruning is achieved by detecting dominance and following the dominance through ancestors up the tree, thus allowing pruning of more than just the dominated node. Although the technique is completely general, the authors don’t mention whether other symmetric constraint programming problems exhibit this property.

The authors do a great job of surveying solutions to the social golfer problem, and of presenting their results. This paper is worth reading for anyone trying to dig deeply into symmetry breaking in constraint programming.