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

 

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

 

Abstract:
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.
\begin{compactitem}[-]

  • 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?
    \end{compactitem}

     

    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.