Partial Symmetry Breaking by Local Search in the Group

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

Research output: Contribution to journalArticlepeer-review

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
Number of pages24
JournalConstraints
Volume17
Issue number2
Early online date20 Mar 2012
DOIs
Publication statusPublished - 2012

Keywords

  • Symmetry breaking
  • Local search
  • Matrix symmetry

Fingerprint

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

Cite this