Comparison of symmetry breaking methods in constraint programming
Karen E. Petrie · 2005
Symmetry in a Constraint Satisfaction Problem can cause wasted search, which can be avoided by adding constraints to the CSP to exclude symmetric assignments or by modifying the search algorithm so that search never visits assignments symmetric to those already considered. One such approach is SBDS (Symmetry Breaking During Search); a modification is GAP-SBDS, which works with the symmetry group rather than individual symmetries. There has been little experience of how these techniques compare in practice. We compare their performance in finding all graceful labellings of graphs with symmetry. For these problems, GAP-SBDS is faster than SBDS unless there are few symmetries. When simple symmetry-breaking constraints can be found to break all the symmetry, GAP-SBDS is slower; if the constraints break only part of the symmetry, GAP-SBDS does less search and is faster. Eliminating symmetry has allowed us to find all graceful labellings, or prove that there are none, for several graphs whose gracefulness was not previously known. 1