Tuesday, 15:15 - 15:40 h, Room: H 3003A


Toby Walsh
Breaking variable and value symmetry in constraint satisfaction and optimisation problems


Factoring out the symmetry in a model is important for solving many constraint satisfaction and optimisation problems. Symmetries can act on the variables, or on the values, or on both the variables and the values in a model.
A simple but nevertheless effective method to deal with symmetry is to post static constraints which eliminate symmetric assignments. If a model has value symmetry in addition to variable symmetry, we might simply post the relevant value symmetry breaking constraints in addition to the variable symmetry breaking constraints.
We consider three issues with this approach.

  • Soundness: Is it safe to post together the variable and value symmetry breaking constraints?

  • Completeness: Does this combination of symmetry breaking constraints eliminate all symmetry from the problem? If not, how can we eliminate all symmetry?

  • Complexity: What is the complexity of breaking all variable and value symmetry? And of propagating the combination of the variable and value symmetry breaking constraints together?


    Talk 1 of the contributed session Tue.3.H 3003A
    "Constraint programming methodology" [...]
    Cluster 5
    "Constraint programming" [...]


  •   There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.