**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"** [...]