propagation between the symmetry breaking and problem constraints, we propose the C&LEX(X, Y , C) constraint. This holds iff C(X), C(Y ) and LEX(X, Y ) all simultaneously hold. To illustrate the potential value of such a C&LEX constraint, we give a simple example where it reduces search super-polynomially.

Example 1. Let M be a n × 3 matrix in which all rows are interchangeable. Suppose that C(**X, Y, Z**) ensures Y = X + Z, and that variable domains are as follows:
M =

{1, . . . , n − 1} {n + 1**, . . . ,** 2n − 1} n
{1, . . . , n − 1} {**n, . . . ,** 2n − 2} n − 1
. . . . . . . . .

{1, . . . , n − 1} {3, . . . , n + 1} 2 {1, . . . , n − 1} {2**, . . . , n**} 1

.

We assume that the branching heuristic instantiates variables top down and left to right, trying the minimum value first. We also assume we enforce DC on posted constraints. If we model the problem with C&LEX constraints, we solve it without search.

On the other hand, if we model the problem with separate LEX and C constraints, we explore an exponential sized search tree before detecting inconsistency using the mentioned branching heuristic and a super-polynomial sized tree with any k-way branching heuristic.

## 3.1 Propagating C&Lex

We now show how, given a (polynomial time) propagator for the constraint C, we can build a (polynomial time) propagator for C&LEX. The propagator is inspired by the DC filtering algorithm for the LEXCHAIN constraint proposed by Carlsson and Beldiceanu [8]. The LEXCHAIN constraint ensures that rows of the matrix M are lexicographically ordered. If the LEXCHAIN constraint is posted on two rows then LEXCHAIN is equivalent to the C&LEX(X, Y, **True)** constraint. However, unlike [8],
we can propagate here a conjunction of the LEX constraint and arbitrary global constraints C. The propagator for the C&LEX constraint is based on the following result which decomposes propagation into two simpler problems.

Proposition 1. Let Xl be the lexicographically smallest solution of C(X), Yu *be the* lexicographically greatest solution of C(Y ), and LEX(Xl, Yu)*. Then enforcing* DC
on C&LEX(X, Y , C) *is equivalent to enforcing* DC on C&LEX(X, Yu, C) *and on* C&LEX(Xl, Y , C) .

Proof. Suppose C&LEX(Xl, Y , C) is DC. We are looking for support for Yk =
v, where Yk is an arbitrary variable in Y . Let Y
′ be a support for Yk = v in C&LEX(Xl, Y , C). Such a support exists because C&LEX(Xl, Y , C) is DC.

C&LEX(Xl, Y , C) ensures that Y
′
is a solution of C(Y ) and LEX(Xl, Y
′
). Consequently, Xl and Y
′
are a solution of C&LEX(X, Y , C). Similarly, we can find a support for Xk = v, where Xk is an arbitrary variable in X. ⊓⊔
Thus, we will build a propagator for C&LEX that constructs the lexicographically smallest (greatest) solution of C(X) (C(Y )) and then uses two simplified C&LEX constraints in which the first (second) sequence of variables is replaced by the appropriate bound.