[full paper] |
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.