k = 1, . . . , i − 1, L[i] **< LX**[i]. After enforcing DC on C(LX), the value v is left in the domain of LX[p]. Consequently, there exists a support for X[p] = v, starting with [L[1], . . . , L[i − 1], v′**, . . .**], v
′ ∈ D(LX[i]), that is strictly greater than L.

Marking at line 13 covers the case where L is a solution of C(X).

2. By contradiction. Suppose that value v ∈ D(X[p]) was not marked by Algorithm 2 but it has a support X′such that L ≤lex X′. Let i be the first position where L[i] < X[i] and L[k] = X[k], k = 1**, . . . , i** − 1. We consider three disjoint cases:
- The case that no such i exists. Then L is a support for value v ∈ D(X[p]).

Hence, value v has to be marked at line 13. This leads to a contradiction.

- The case that i ≤ n and **p < i**. Note that in this case v equals L[p]. Consider Algorithm 2 at step i. At this point we have L[k] = LX[k], k = 1**, . . . , i** − 1.

After enforcing DC on C(LX) (line 7), values X′[k], i = 1**, . . . , n** are left in the domain of LX, because L[i] < X′[i], L[k] = X′[k], k = 1**, . . . , i** − 1. Hence, value v ∈ X′[p] will be marked at line 7. This leads to a contradiction.

- The case that i ≤ n and i ≤ p. Consider Algorithm 2 at step i. At this point we have L[k] = LX[k], k = 1**, . . . , i** − 1. Moreover, value X′[i] has to be in the domain of LX[i], because value X′[i] is greater than L[i] and is consistent with the partial assignment [L[1], . . . , L[i − 1]]. Domains of variables LX contain all values that have supports starting with [L[1], . . . , L[i − 1]] and are strictly greater than L. Consequently, they contain X′[i], i = 1**, . . . , n** and the algorithm marks v at line 7. This leads to a contradiction.

⊓⊔
A filtering algorithm for the C&LEX(**X, Y , C**). Algorithm 4 enforces domain consistency on the C&LEX(X, Y , C) constraint. Following Proposition 1, Algorithm 4 finds the lexicographically smallest (greatest) solutions for C(X) (C(Y )) and runs a relaxed version of C&LEX for each row. Algorithm 4 gives the pseudo-code for the propagator for the C&LEX(X, Y , C) constraint.

Algorithm 4 C&LEX(X, Y , C)

![0_image_0.png](0_image_0.png)

1: **procedure** C&LEX(X : out, Y : **out, C** : in)
2: if (Cmin(Xl, X) == fail) or (Cmax(Y , Yu)) == fail) **then**
3: return **false**;
4: if (Xl >lex Yu) **then**
5: return **false**;
6: C&LEXlb(Xl, Y , C); 7: C&LEXub(X, Yu, C);

## Proposition 4. Algorithm 4 Enforces Dc On The C&Lex(X, Y , C) Constraint.

Proof. Correctness of the algorithm follows from correctness of the decomposition
(Proposition 1). However, we need to consider the case where Xl >lex Yu, prove correctness of the C&LEXlb and C&LEXub algorithms and prove that the algorithm only needs to run once.