This eliminates solutions (2) and (3). Finally, eliminating
the third symmetry where we both reverse the solution and
subtract it from 10 is more difficult. We can, for instance,
post:
$$X_{1}\leq10-X_{11},$$ $$X_{1}=10-X_{11}\Rightarrow X_{2}\leq10-X_{10},$$ $$X_{1}=10-X_{11}\ \&\ X_{2}=10-X_{10}\Rightarrow X_{3}\leq10-X_{9},$$ $$\vdots\tag{7}$$
Note that of the four symmetric solutions given earlier, only
(4) with X1 = 2, X2 = 8 and X11 = 7 satisfies all three sets of symmetry breaking constraints: (5), (6) and (7). The other three solutions are eliminated. This leaves the question of where symmetry breaking constraints like (6) and (7) come from in general. Our work helps answer this question.

## Formal Background

A constraint satisfaction problem consists of a set of variables, each with a domain of values, and a set of constraints specifying allowed combinations of values for given subsets of variables. Variables take one value from a given finite set. A solution is an assignment of values to variables satisfying the constraints. Symmetry occurs in many constraint satisfaction problems. A *value symmetry* is a permutation of the values that preserves solutions. More formally, a value symmetry is a bijective mapping, σ of the values such that if X1 = d1**, . . . , X**n = dn is a solution then X1 = σ(d1)**, . . . , X**n = σ(dn) is also. For example, in the all interval series problem, the value symmetry σ maps the value i onto n − 1 − i. A *variable symmetry*, on the other hand, is a permutation of the variables that preserves solutions. More formally, a variable symmetry is a bijective mapping, θ of the indices of variables such that if X1 = d1**, . . . , X**n = dn is a solution then Xθ(1) = d1**, . . . , X**θ(n) = dn is also. For example, in the all interval series problem, the variable symmetry for reversing a series maps the index i onto n − i + 1. Symmetries are problematic as they increase the size of the search space. For instance, m interchangeable values increases the size of the search space by a factor of m!.

## Lex-Leader Method

One simple and effective mechanism to deal with symmetry is to add constraints which eliminate symmetric solutions (Puget 1993). For variable symmetries, Crawford et al. give a simple method that eliminates all symmetric solutions (Crawford *et al.* 1996). The basic idea is very simple.

We pick an ordering on the variables, and then post symmetry breaking constraints to ensure that the final solution is lexicographically less than any symmetric re-ordering of the variables. For example, with a reversal symmetry which maps Xito Xn−i+1, we post the lexicographical ordering constraint:
[X1, . . . , Xn] ≤lex [Xn**, . . . , X**1]
This selects the "lex leader" assignment. Note that if Xi are all-different, as they are in the all interval series problem, we can simplify this lex leader constraint to give as in (5):

## X1 < Xn

The lex-leader method lies at the heart of most static methods for breaking variable symmetry. In their survey of symmetry breaking in constraint programming in the recent Handbook of Constraint Programming, Gent, Petrie and Puget observe that:
". . . *lex-leader remains of the highest importance, because there a number of ways it is used to derive new symmetry breaking methods . . . [however] the* lex-leader method is defined only for variable symmetries . . . a proper generalisation of lex-leader to deal with value symmetries would be valuable, even if restricted to some special cases . . . " page 345
(Gent, Petrie, & Puget 2006) This is the research challenge we have been tackling in our recent work (Walsh 2006a; Walsh 2007).

## Value Symmetry

In (Walsh 2006a), we propose a generalization of the lexleader method that works with any type of value symmetry. Suppose we have a set Σ of value symmetries. We can eliminate all symmetric solutions with the constraint VALSYM(Σ, [X1**, . . . , X**n]) which ensures for all σ ∈ Σ:
[X1, . . . , Xn] ≤lex [σ(X1)**, . . . , σ**(Xn)] (8)
Where X1 to Xn is any fixed ordering on the variables and σ(Xi) represents the action of the symmetry σ on the value assigned to Xi. For example, if σ inverts values by mapping i onto n − 1 − i as in the all interval series, we can simplify
(8) to give:

$\mathbf{t}=1$
[X1, X2, . . .] ≤lex [n − 1 − X1, n − 1 − X2**, . . .**]

$$n-1-X_{1}$$

Expanding the definition of lex, and exploiting the fact that X1 6= X2, we get as in (6): X1 ≤ n − 1 − X1, X1 = n − 1 − X1 ⇒ X2 < n − 1 − X2 We give a linear time propagator for lex-leader constraints like (8), and show how to extend the lex-leader method to symmetries which act on both variables and values simultaneously.

In theory, this generalization of the lex-leader method solves the problem of value symmetries as it eliminates all symmetric solutions. Unfortunately, several problems remain. First, the set of symmetries Σ can be exponentially large (for example, there are m! symmetries if we have m interchangeable values) requiring us to post a large number of lex ordering constraints. Second, decomposing VALSYM
into separate lex ordering constraints hinders propagation and may prevent all symmetric values from being pruned.

In (Walsh 2006a), we give a simple example where this decomposition hinders propagation. Somewhat surprisingly, there is little hope to overcome this second problem. We prove in (Walsh 2007) that pruning all symmetric values is intractable in general even with a small number of symmetries (assuming P 6= NP).