2010/05/28 by George Katsirelos, Katsirelos, George, Toby Walsh +1
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #I.2.4 #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.1005.5270
openalex publication_date 2010/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Symmetry is an important feature of many constraint programs. We show that any problem symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. This simple but powerful idea can be used in a number of different ways. We describe one application within model restarts, a search technique designed to reduce the conflict between symmetry breaking and the branching heuristic. In model restarts, we restart search periodically with a random symmetry of the symmetry breaking constraints. Experimental results show that this symmetry breaking technique is effective in practice on some standard benchmark problems.