Boosting Partial Symmetry Breaking by Local Search

Steven Prestwich, Brahim Hnich, Helmut Simonis, Roberto Rossi, S Armagan Tarim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009)
Publication statusPublished - 2009
Event9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009) - Lisbon, Portugal
Duration: 21 Sep 2009 → …

Workshop

Workshop9th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2009)
CountryPortugal
CityLisbon
Period21/09/09 → …

Fingerprint Dive into the research topics of 'Boosting Partial Symmetry Breaking by Local Search'. Together they form a unique fingerprint.

Cite this