each assignment down any branch in the search tree. For this reason, it is meaningful to compute the total amortised cost of enforcing a local consistency down an entire branch of the search tree so as to capture the incremental cost of propagation. We will compute complexities in this way.

3 ALL-DIFFERENT **constraint**
The ALL-DIFFERENT constraint is one of the most useful
global constraints available to the constraint programmer. For
instance, it can be used to specify that activities sharing the
same resource take place at different times. A central concept in propagating the ALL-DIFFERENT constraint is the notion
of a *Hall interval*. This is an interval of m domain values
which completely contains the domains of m variables. [a, b]
is a Hall interval iff |{i | dom(Xi) ⊆ [a, b]}| = b − a + 1.
In any bound support, the variables whose domains are contained within the Hall interval consume all the values in the
Hall interval, whilst any other variables must find their support outside the Hall interval.
Example 1. *Consider an* ALL-DIFFERENT constraint over the following variables and values:
$\begin{array}{cccccc}\hline&3&4&5\\ \hline&*&*&\\ &*&*&\\ &*&*&*\\ &*&*&*\\ \hline\end{array}$  . 
X1 ∗ ∗ X2 ∗ ∗ ∗ ∗ X3 ∗ ∗
X4 ∗ ∗ ∗ ∗
[1, 1] is a Hall interval of size 1 as the domain of 1 variable, X5 is completely contained within it. Therefore we can
remove [1, 1] from the domains of all the other variables. This
leaves X2 *with a domain containing values 2,3,4.*
[3, 4] *is a Hall interval of size 2 as it completely contains*
the domains of 2 variables, X1 and X3*. We can thus remove*
[3, 4] from the domains of X2 and X4*. This leaves the following range consistent domains:*
Enforcing bound consistency on the same problem does not
create holes in domains. That is, it would leave X4 with the
values 2,3,4,5.
To identify and prune such Hall intervals from the domains
of other variables, Leconte has proposed a RC propagator for
the ALL-DIFFERENT constraint [Leconte, 1996] that runs in
Θ(n
2) time. We now propose a simple decomposition of the
$\begin{array}{c}\includegraphics[height=56.905512pt]{Fig1}\\ \hline X_1\\ X_2\\ X_3\\ X_4\\ X_5\end{array}$ . 
ALL-DIFFERENT constraint which permits us to enforce RC.
The decomposition ensures that no interval can contain more
variables than its size. We introduce O(nd2) new 0/1 variables, Ailu to represent whether Xitakes a value in the interval [l, u]. For 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d and u − l < n, we
post the following constraints:
 Ning constraints:  $\begin{array}{llllll}A_{ilu}=1&\iff&X_i\in[l,u]&\qquad&\textrm{(1)}\\ &\\ \sum_{i=1}^n A_{ilu}&\leq&u-l+1&\qquad&\textrm{(2)}\\ \end{array}$  I think you can't know how to solve it. 
1 2 3 4 5 X1 ∗ ∗ X2 ∗ X3 ∗ ∗ X4 ∗ ∗ X5 ∗

We illustrate this decomposition on our running example.

Example 2. *Consider again the last example (i.e. an* ALL-DIFFERENT *constraint on* X1 ∈ [3, 4], X2 ∈ [1, 4],
X3 ∈ [3, 4], X4 ∈ [2, 5] and X5 ∈ [1, 1]).

First take the interval [1, 1]. Since X5 ∈ [1, 1]*, (1) implies* A511 = 1*. Now from (2),* P4 i=1 Ai11 ≤ 1*. That is, at most* one variable can take a value within this interval. This means that A211 = 0*. Using (1) and* A211 = 0*, we get* X2 6∈ [1, 1].

Since X2 ∈ [1, 4], this leaves X2 ∈ [2, 4].

Now take the interval [3, 4]*. From (1),* A134 = A334 = 1.

Now from (2), P4 i=1 Ai34 ≤ 2*. That is, at most 2 variables can take a value within this interval. This means that* A234 = A434 = 0*. Using (1) we get* X2 6∈ [3, 4], X4 6∈ [3, 4]. Since X2 ∈ [2, 4] and X4 ∈ [2, 5]*, this leaves* X2 = 2 and X4 ∈ {2, 5}*. Local reasoning about the decomposition has thus made the original* ALL-DIFFERENT constraint range consistent.

We will prove that enforcing DC on the decomposition enforces RC on the original ALL-DIFFERENT constraint. We find it surprising that a simple decomposition like this can simulate a complex propagation algorithm like Leconte's. In addition, the overall complexity of reasoning with the decomposition is similar to Leconte's propagator. Theorem 1. *Enforcing DC on constraints (1) and (2) enforces RC on the corresponding* ALL-DIFFERENT constraint in O(nd3) *down any branch of the search tree.*
Proof: [Leconte, 1996] provides a necessary and sufficient condition for RC of the ALL-DIFFERENT constraint: every Hall interval should be removed from the domain of variables whose domains are not fully contained within that Hall interval. Let [a, b] be a Hall interval. That is, |H| = b − a + 1 where H = {i | dom(Xi) ⊆ [a, b]}. Constraint (1) fixes Aiab = 1 for all i ∈ H. The inequality (2) with l = a and u = b becomes tight fixing Aiab = 0 for all i 6∈ H. Constraint (1) for l = a, u = b, and i 6∈ H removes the interval
[a, b] from the domain of Xi as required for RC.

There are O(nd2) constraints (1) that can be woken O(d)
times down the branch of the search tree. Each propagation requires O(1) time. Constraints (1) therefore take O(nd3)
down the branch of the search tree to propagate. There are O(d 2) constraints (2) that each take O(n) time to propagate down the branch of the search tree for a total of O(nd2)
time. The total running time is given by O(nd3) +O(nd2) =
O(nd3). ✷
Note that if we use a solver in which we can specify that constraints only wake on reaching a particular bound, we can decrease to O(1) the number of times constraints (1) are woken, which gives a total complexity in O(nd2).

What about bound consistency of the ALL-DIFFERENT
constraint? By using a representation that can only prune bounds [Ohrimenko *et al.*, 2007], we can give a decomposition that achieves BC in a similar way. In addition, we can reduce the overall complexity in the case that constraints are woken whenever their bounds change. We introduce new 0/1 variables, Bik, 1 ≤ k ≤ d and replace (1) by the following constraints:

$$B_{il}=1\quad\Longleftrightarrow\quad X_{i}\leq l\tag{3}$$ $$A_{ilu}=1\quad\Longleftrightarrow\quad(B_{i(l-1)}=0\wedge B_{iu}=1)\tag{4}$$
