Projects per year
Abstract
Variable symmetries in a constraint satisfaction problem can be broken by adding lexicographic ordering constraints. Existing general methods of generating such sets of ordering constraints can require a huge number of constraints. This adds an unacceptable overhead to the solving process. Methods exist by which this large set of ordering constraints can be reduced to a much smaller set automatically, but their application is also prohibitively costly. In contrast, this paper takes a bottomup approach. It examines some commonlyoccurring families of groups and derives a minimal set of ordering constraints sufficient to break the symmetry each group describes. These minimal sets are then used as building blocks to generate minimal sets of ordering constraints for groups constructed via direct and imprimitive wreath products. Experimental results confirm the value of minimal sets of ordering constraints, which can now be generated much more cheaply than with previous methods.
Original language  English 

Pages (fromto)  75102 
Number of pages  28 
Journal  Annals of Mathematics and Artificial Intelligence 
Volume  57 
Issue number  1 
DOIs  
Publication status  Published  Sept 2009 
Keywords
 Constraint programming
 Constraint modelling
 Symmetry
Fingerprint
Dive into the research topics of 'Minimal ordering constraints for some families of variable symmetries'. Together they form a unique fingerprint.Projects
 2 Finished

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
1/09/05 → 31/08/10
Project: Standard

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A., Gent, I. P., Leonhardt, U., Mackenzie, A., Miguel, I. J., Quick, M. & Ruskuc, N.
1/09/05 → 31/08/10
Project: Standard