This does not change the asymptotic complexity of reasoning with the decomposition, nor does it improve the level of propagation achieved. However, we have found that the fixed point of propagation is reached quicker in practice with such an implied constraint.

Our second improvement decreases the asymptotic complexity of enforcing BC on the decomposition of Section 4. The complexity is dominated by reasoning with constraints (4) which channel from Xito Ailu and thence onto Mlu (through constraints
(5)). If constraints (4) are not woken uselessly, enforcing BC costs O(1) per constraint down the branch. Unfortunately, existing solvers wake up such constraints as soon as a bound is modified, thus giving 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 [5] 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). Instead we extend 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)