Minimal ordering constraints for some families of variable symmetries

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)75-102
Number of pages28
JournalAnnals of Mathematics and Artificial Intelligence
Volume57
Issue number1
DOIs
Publication statusPublished - 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.

Cite this