Symmetry breaking in constraint programming

Abstract

We describe a method for symmetry breaking during search (SBDS) in constraint programming. It has the great advantage of not interfering with heuristic choices. It guarantees to return a unique solution from each set of symmetrically equivalent ones, which is the one found first by the variable and value ordering heuristics. We describe an implementation of SBDS in ILOG Solver, and applications to low autocorrelation binary sequences and the n-queens problem. We discuss how SBDS can be applied when there are too many symmetries to reason with individually, and give applications in graph colouring and Ramsey theory.