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)

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 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
JournalConstraints
Volume17
Issue number2
DOIs
Publication statusPublished - 2012

Keywords

  • constraint satisfaction
  • lex

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

  • Cite this

    Prestwich, S., Hnich, B., Simonis, H., Rossi, R., & Tarim, S. A. (2012). Partial Symmetry Breaking by Local Search in the Group. Constraints, 17(2), 148-171. https://doi.org/10.1007/s10601-012-9117-z