preprocessed. The pruning can only create equality of lower bounds or upper bounds for some precedence constraints. The assignment X3 = 1 demonstrates this situation in Example 2. Direct pruning of X3 = 1 forces lower bounds of X1 and X2, that are in the precedence relation, to be equal.

As domains Ddp v
(X1), . . . , Ddp v
(Xn) are preprocessed, we know that the greedy algorithm (Section 4) will find a solution of ALLDIFFERENT on the domains Ddp v
(X1), . . . , Ddp v
(Xn) that also satisfies the precedence constraints if a solution exists. This solution is a support for Xi = v. ut Based on Lemma 2 we prove that we can enforce bounds consistency on the ALLDIFFPREC constraint in O(n 2). However, we start with a simpler and less efficient algorithm to explain the idea . We show how to improve this algorithm in the next section. Given Lemma 2, the most straightforward algorithm to enforce bounds consistency for Xi = v is to assign Xito v, perform the direct pruning, run the greedy algorithm and, if it fails, prune v. Interestingly enough, to detect bounds disentailment we do not have to run a greedy algorithm for each pair Xi = v. If the ALLDIFFERENT
constraint and the precedence constraints are bounds consistent, we show that it is sufficient to check that a set of conditions (5)-(10) holds for each interval of values. If these conditions are satisfied then the pair Xi = v is bounds consistent. Hence, for each pair Xi = v, 1 ≤ i ≤ n, v ∈ D(Xi), and for each interval we enforce the following conditions. We assume that ∪
n i=1D(Xi) = [1, d]. For Xi, 1 ≤ i ≤ n, v ∈ D(Xi)
and for all intervals [*v, v* + k] and [v − *p, v*], k ∈ [max(Xi) − v + 1, d − v] and p ∈ [v − min(Xi) + 1, v − 1], the following conditions have to be satisfied:

$$B^{i}_{1,v+k}=|\{j\in S(i)|\mathcal{D}(X_{j})\subseteq[1,v+k]\}|\tag{5}$$ $$D^{i}_{v,(v+k)}=|\{j\notin S(i)|\mathcal{D}(X_{j})\subseteq[v,v+k]\}|$$ (6) $$B^{i}_{1,v+k}+D^{i}_{v,(v+k)}\leq k$$ (7) $$B^{i}_{v-p,d}=|\{j\in P(i)|\mathcal{D}(X_{j})\subseteq[v-p,d]\}|$$ (8) $$D^{i}_{v-p,v}=|\{j\notin P(i)|\mathcal{D}(X_{j})\subseteq[v-p,v]\}|$$ (9) $$B^{i}_{v-p,d}+D^{i}_{v-p,v}\leq p\tag{10}$$

Note that we actually do not have to consider all possible intervals. For every variable-value pair Xi = v we consider all intervals [*v, u*], u ∈ [max(Xi) + 1, d] and all intervals [*l, v*], l ∈ [1, min(Xi) − 1]. The parameter k (p) is used to slide between intervals [*v, u*], u ∈ [max(Xi) + 1, d] ([*l, v*], l ∈ [1, min(Xi) − 1]). Equations (5)–(7)
make sure that the number of variables that fall into an interval [*v, u*], after the assignment Xito v, is less than or equal to the length of the interval minus 1. Symmetrically, Equations (8)–(10) ensure that the same condition is satisfied for all intervals [*l, v*]. If there exists an interval [v, u]([*l, v*]) that violates the condition for a pair Xi = v then this interval is removed from D(Xi).

Example 3 *Consider* ALLDIFFPREC([X1, X2, X3, X4, X5], {(1, 2),(1, 3)})*. Domains of the variables are* D(X1) = [1, 5], D(X2) = D(X3) = [2, 6] and D(X4) = D(X5) = [3, 6]*. Consider a variable-value pair* X1 = 3*. By the direct pruning we get the following domains:* D
dp 3
(X1) = 3, D
dp 3
(X2) = [4, 6], D
dp 3
(X3) = [4, 6],