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 bottom-up approach. It examines some commonly-occurring 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 (from-to) | 75-102 |
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
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
1/09/05 → 31/08/10
Project: Standard
-
EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Ruskuc, N. (PI) & Quick, M. (CoI)
1/09/05 → 31/08/10
Project: Standard