
## 5 Bounds Consistency

We present an algorithm that enforces bounds consistency on the ALLDIFFPREC constraint. First, we consider an assignment Xi = v and a partial filtering that this assignment causes. We call this filtering *direct pruning* caused by the assignment Xi = v or, in short, direct pruning of Xi = v. Informally, direct pruning works as follows. If Xitakes v then the value v becomes unavailable for the other variables due to the ALLDIFFERENT constraint. Hence, we remove v from the domains of variables that have v as their lower bound or upper bound. Due to precedence constraints, we increase the lower bounds of successors of Xito v + 1 and decrease the upper bounds of predecessors of Xito v − 1. Note that direct pruning *does not enforce* bounds consistency on either ALLDIFFPREC or the single ALLDIFFERENT constraint. However, direct pruning is sufficient to detect bounds inconsistency as we show below.

Let P(i) and S(i) be the sets of variables that precede and succeed Xi, respectively. We denote the domains obtained after direct pruning of Xi = v as Ddp v
(X1), . . . , Ddp v
(Xn), so that for all j = 1*, . . . , n*:

$$\mathcal{D}_{v}^{dp}(X_{j})=\mathcal{D}(X_{j})\setminus\{v\}\text{if}j\neq i,v\in\{\min(X_{j}),\max(X_{j})\}\tag{1}$$ $$\mathcal{D}_{v}^{dp}(X_{j})=v\text{if}j=i,$$ (2) $$\mathcal{D}_{v}^{dp}(X_{j})=\mathcal{D}(X_{j})\setminus[v,max(X_{j})]\text{if}j\in P(i),$$ (3) $$\mathcal{D}_{v}^{dp}(X_{j})=\mathcal{D}(X_{j})\setminus[min(X_{j}),v]\text{if}j\in S(i).\tag{4}$$

These bounds could be pruned further but we will first analyze the properties that this simple filtering offers.

Example 2 *Consider* ALLDIFFPREC([X1, X2, X3], {(1, 2)}) *constraint with* D(X1) = {1, 2}, D(X2) = {2, 3}, D(X3) = {1, 2, 3}*. For example, an assignment* X1 = 2 *results in the domains:* D
dp 2
(X1) = {2}, D
dp 2
(X2) = {3} and D
dp 2
(X3) = {1, 2, 3}. We point out again that we can continue pruning as values 2 and 3 *have to be removed from* D
dp 2
(X3)*. However, direct pruning of* X1 = 2 *is sufficient* for our purpose. Consider another example. An assignment X3 = 1 *results in the* domains: D
dp 3
(X1) = {2}, D
dp 3
(X2) = {2, 3} and D
dp 3
(X3) = {1}.

Our algorithm is based on the following lemma.

Lemma 2 Let ALLDIFFERENT *and precedence constraints be bounds consistent over* variables X, Xi = v, v ∈ {min(Xi), max(Xi)} *be an assignment of a variable* Xito its bound and Ddp v
(X1)*, . . . ,* Ddp v
(Xn) *be the domains after direct pruning of* Xi = v.

Then, Xi = v *is bounds consistent iff* ALLDIFFERENT([X1, . . . , Xn]), where domains of variables X are Ddp v
(X1)*, . . . ,* Ddp v
(Xn)*, has a solution.*
Proof: Suppose ALLDIFFERENT and the precedence constraints are bounds consistent. As precedence constraints are bounds consistent, we know that for all (*i, j*) ∈ E,
Xi < Xj , min(Xi) < min(Xj ) and max(Xi) < max(Xj ). Consider direct pruning of Xi = v. Note, direct pruning of Xi = v preserves the property of domains being