Symmetry Breaking by Metaheuristic Search

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

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

Abstract

Several methods exist for breaking symmetry in constraint problems, but most potentially suffer from high memory requirements, high computational overhead, or both. We describe a new partial symmetry breaking method that can be applied
to arbitrary variable/value symmetries. It models dominance detection as a nonstationary optimisation problem, and solves it by resource-bounded
metaheuristic search in the symmetry group. It has low memory requirement and computational overhead, yet in preliminary experiments on BIBD design it breaks most symmetries.
Original languageEnglish
Title of host publicationProceedings of the 8th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2008)
Publication statusPublished - 2008
Event8th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2008) - Sydney, Australia
Duration: 14 Sept 2008 → …

Conference

Conference8th International Workshop on Symmetry and Constraint Satisfaction Problems (SYMCON 2008)
Country/TerritoryAustralia
CitySydney
Period14/09/08 → …

Fingerprint

Dive into the research topics of 'Symmetry Breaking by Metaheuristic Search'. Together they form a unique fingerprint.

Cite this