constraint down the branch. Unfortunately, existing solvers wake up such constraints as soon as a bound is modified, thus a cost in O(d). We therefore implemented a specialized propagator to channel between Xi and Mlu efficiently. To be more precise, we remove the O(nd2) variables Ailu and replace them with O(nd) Boolean variables Zij .

We then add the following constraints

$$\begin{array}{c c c}{{Z_{i j}=1\,\Longleftrightarrow X_{i}\leq j}}&{{}}&{{1\leq j\leq d}}\\ {{Z_{i(l-1)}=1\lor Z_{i u}=0\lor M_{l u}>0}}&{{}}&{{1\leq l\leq u\leq d,1\leq i\leq n}}\end{array}$$
$$\begin{array}{l}{(9)}\\ {(10)}\end{array}$$

These constraints are enough to channel changes in the bounds of the X variables to Mlu. There are O(nd) constraints (9), each of which can be propagated in time O(d)
over a branch, for a total of O(nd2). There are O(nd2) clausal constraints (10) and each of them can be made BC in time O(1) down a branch of the search tree, for a total cost of O(nd2). Since channeling dominates the asymptotic complexity of the entire decomposition of Section 4, this improves the complexity of this decomposition to O(nd2).

This is similar to the technique used in [6] to improve the asymptotic complexity of the decomposition of the ALL-DIFFERENT constraint.

Our third improvement is to enforce stronger pruning by observing that when Mlu = 0, we can remove the interval [**l, u**] from all variables, regardless of whether this modifies their bounds. This corresponds to enforcing RC on constraints (4). Interestingly, this is sufficient to achieve RC on the ATMOSTNVALUE constraint. Unfortunately, constraints (10) cannot achieve this pruning and using constraints (4) increases the complexity of the decomposition back to O(nd3). We do it by extending the decomposition with O(d log d) Boolean variables Bil(l+2k) ∈ [0, 1], 1 ≤ i ≤ n, 1 ≤ l ≤
d, 0 ≤ k ≤ ⌊log d⌋. The following constraint ensures that Bijj = 1 ⇐⇒ Xi = j.

## Domainbitmap(Xi, [Bi11, . . . , Bidd]) (11)

Clearly we can enforce RC on this constraint in time O(d) over a branch, and O(nd)
for all variables Xi. We can then use the following clausal constraints to channel from variables Mlu to these variables and on to the X variables. These constraints are posted for every 1 ≤ i ≤ n, 1 ≤ l ≤ u ≤ d, 1 ≤ j ≤ d and integers k such that 0 ≤ k ≤
⌊log d⌋:

$$\begin{array}{c c}{{B_{i j(j+2^{k+1}-1)}=1\lor B_{i j(j+2^{k}-1)}=0}}\\ {{B_{i j(j+2^{k+1}-1)}=1\lor B_{i(j+2^{k})(j+2^{k+1}-1)}=0}}\\ {{M_{l u}\neq0\lor B_{i l(l+2^{k}-1)}=0}}&{{2^{k}\leq u-l+1<2^{k+1}}}\\ {{M_{l u}\neq0\lor B_{i(u-2^{k}+1)u}=0}}&{{2^{k}\leq u-l+1<2^{k+1}}}\end{array}$$
k+1 (14)
k+1 (15)
The variable Bil(l+2k−1), similarly to the variables Alu, is true when Xi ∈ [**l, l** +
2 k−1], but instead of having one such variable for every interval, we only have them for intervals whose length is a power of two. When Mlu = 0, with 2 k ≤ u − l + 1 < 2 k+1, the constraints (14)–(15) set to 0 the B variables that correspond to the two intervals of length 2 kthat start at l and finish at u, respectively. In turn, the constraints (12)–(13)