GAPLex: Generalised Static Symmetry Breaking

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.