Partial symmetry breaking by local search in the group

Creative Commons License

Prestwich S. D., HNİCH B., Simonis H., Rossi R., TARIM Ş. A.

CONSTRAINTS, cilt.17, sa.2, ss.148-171, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 17 Sayı: 2
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1007/s10601-012-9117-z
  • Dergi Adı: CONSTRAINTS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.148-171
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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.