Symmetry Breaking Revisited

Symmetries in constraint satisfaction problems (CSPs) are one of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of the search tree. This method can be seen as an improvement of the nogood recording presented by Focacci and Milano[5] and Fahle, Schamberger and Sellmann[4]. We present a simple formalization of our method for which we prove correctness and completeness results. We also show that our method is theoretically more efficient as the number of dominance checks, the number of nogoods and the size of each nogood are smaller. This is confirmed by an experimental evaluation on the social golfer problem, a very difficult and highly symmetrical real world problem. We are able to break all symmetries for problems with more than 1036 symmetries. We report both new results, and a comparison with previous work.