The presence of symmetry in constraint satisfaction problems can cause a great deal of wasted search effort, and several methods for breaking symmetries have been reported. In this paper we revisit a recent method called Symmetry Breaking by Nonstationary Optimisation (SBNO) which interleaves incomplete search in the symmetry group with backtrack search on the constraint problem. We provide a more accurate characterisation of SBNO, extend it to arbitrary symmetries and constraint solvers, reimplement it in a real constraint solver, combine it with double-lex symmetry breaking, and show that this combination is one of the most scalable known methods for a class of highly symmetric problems. We believe that SBNO is most useful as a method for boosting other partial symmetry breaking methods on highly symmetric problems, because of its potential use of the entire symmetry group, low memory requirement and computational overhead.
|Title of host publication||Proceedings of the 9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009)|
|Publication status||Published - 2009|
|Event||9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009) - Lisbon, Portugal|
Duration: 21 Sep 2009 → …
|Workshop||9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009)|
|Period||21/09/09 → …|