Projects per year
Abstract
Constraint Satisfaction Problems (CSPs) are often highly symmetric. Symmetries can give rise to redundant search, since subtrees may be explored which are symmetric to subtrees already explored. To avoid this redundant search, constraint programmers have designed methods, which try to exclude all but one in each equivalence class of solutions. One problem with many of the symmetry breaking methods that eliminate all the symmetry is that they can have a large running overhead. To counter this flaw many CP practitioners have looked for methods that only eliminate a subset of the symmetries, so called partial symmetry breaking methods, but do so in an efficient manner. Partial symmetry breaking methods often work only when the problem is of a certain type. In this paper, we introduce a new method of finding a small set of constraints which provide very efficient partial symmetry breaking. This method works with all problem classes and modelling techniques.
Original language  English 

Title of host publication  Principles and Practice of Constraint Programming  CP 2011 
Editors  Jimmy Lee 
Publisher  Springer 
Pages  729743 
Number of pages  15 
Volume  6876 
ISBN (Print)  9783642237850 
DOIs  
Publication status  Published  2011 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer Berlin / Heidelberg 
Fingerprint
Dive into the research topics of 'Automatic Generation of Constraints for Partial Symmetry Breaking'. Together they form a unique fingerprint.Projects
 1 Finished

A Constraint Solver Synthesiser: A Constraint Solver Synthesiser
Miguel, I. J. (PI), Balasubramaniam, D. (CoI), Gent, I. P. (CoI), Kelsey, T. (CoI) & Linton, S. A. (CoI)
1/10/09 → 30/09/14
Project: Standard