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 SBDD method presented by Focacci and Milano 7] and Fahle, Schamberger and Sellmann 5]. We present a simple formalization of our method for which we prove correctness and completeness results. We show that our method is theoretically more efficient as the size of each no-good is smaller. This theoretical analysis is confirmed by thorough experimental evaluation on highly symmetrical real world problems. We are able to break all symmetries for problems with more than 10⁷⁸ symmetries.