GAPLex: Generalised Static Symmetry Breaking

Research output: Contribution to conferencePaper

Abstract

We describe a novel algorithm that statically breaks symmetry in CSPs by using computational group theory during search. This algorithm extends and generalises the commonly used double lex method for breaking symmetry in matrices. We showthat our new symmetry breaking method, GAPLex, is sound (will neither lose solutions nor return incorrect solutions) and complete (will return exactly one member from each class of symmetrically equivalent solutions). We demonstrate that our implementation of GAPLex is competitive with other methods, being effectively applicable to CSPs with large domains and less than full variable and/or value symmetry. We also describe how GAPLex can be combined with incomplete symmetry breaking methods such as double-lex to provide fast and complete symmetry breaking. We believe this to be the rst method that successfully combines the posting of symmetry breaking constraints before search, with symmetry breaking by analysis of search states.
Original languageEnglish
Pages17-23
Publication statusPublished - Sept 2006
EventSymCon'06: The Sixth International Workshop on Symmetry and Constraint Satisfaction Problems - Nantes, France
Duration: 25 Sept 2006 → …

Conference

ConferenceSymCon'06: The Sixth International Workshop on Symmetry and Constraint Satisfaction Problems
Country/TerritoryFrance
CityNantes
Period25/09/06 → …

Fingerprint

Dive into the research topics of 'GAPLex: Generalised Static Symmetry Breaking'. Together they form a unique fingerprint.

Cite this