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. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.