Partial Symmetry Breaking by Local Search in the Group

S. Prestwich, B. Hnich, H. Simonis, R. Rossi, S.A. Tarim

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)


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 describe a new method called Symmetry Breaking by Nonstationary Optimisation, which interleaves local search in the symmetry group with backtrack search on the constraint problem. It can be tuned to break each symmetry with an arbitrarily high probability with high runtime overhead, or as a lightweight but still powerful method with low runtime overhead. It has negligible memory requirement, it combines well with static lex-leader constraints, and its benefit increases with problem hardness.
Original languageEnglish
Pages (from-to)148-171
Issue number2
Publication statusPublished - 2012


  • constraint satisfaction
  • lex


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

Cite this