ECAI-2000 Logo

ECAI-2000 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Symmetry Breaking in Constraint Programming

Ian P. Gent, Barbara M. Smith

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.

Keywords: Constraint Programming, Constraint Satisfaction

Citation: Ian P. Gent, Barbara M. Smith: Symmetry Breaking in Constraint Programming. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.599-603.

[prev] [tofc] [next]

ECAI-2000 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Humboldt University on behalf of Gesellschaft für Informatik.