Symmetry Breaking During Search in Constraint Programming
Research Report 99.02, School of Computer Studies, University of Leeds,
January 1999.
Ian P. Gent and Barbara M Smith
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.
Back to "Barbara Smith
- Publications on Constraint Programming"