Algorithm 1: PruneUpperBounds(X1*, . . . , X*n)
1 Sort variables such that max(D(Xi)) ≤ max(D(Xi+1));
2 for i ∈ 1..n do 3 Create a disjoint set data structure T with the integers 1..d; 4 b ← max(D(X1)) + 1; 5 Invariant: b is the smallest value such that there are exactly as many available values in the open-interval [b, max(D(Xj )) + 1) as there are successors of Xi that have been processed.;
6 for Xj *in non-decreasing order of upper bound* do 7 if j 6∈ S(i) **then**
8 S ← Find(min(D(Xj )), T);
9 v ← min(S);
10 Union(v, max(S) + 1, T);
11 if j > 1 **then**
12 for k ∈ 1.. max(D(Xj )) − max(D(Xj−1)) do 13 b ← max(F ind(*b, T*)) + 1; 14 if *F ind(v, T*) = F ind(b, T) ∨ v > b ∨ j ∈ S(i) **then**
15 b ← min(*F ind(b* − 1, T));
16 max(D(Xi)) ← min(max(D(Xi)), b − 1);

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Proof: Consider a violated interval [*v, v*+k]. In this case Bi1,v+k +Div,v+k > k. There exists an interval [l, u] ⊆ [*v, v* + k] such that *l, u* ∈ L ∪ U . We take the largest interval
[*l, u*]. Note that such an interval always exists as the interval [max(Xi), max(Xi)] is contained inside the interval [*v, v* + k]. The interval [*l, u*] also violates the conditions, because it contains the same variables. So, we have Bi1,u + Di l,u > u − l. We note that Di l,u = Div,v+k as there are no lower bounds in the interval [*v, l*). Similarly, there are no upper bounds in the interval (*u, v* + k]. Hence, Bi1,u = Bi1,v+k
. Therefore, Bi1,u + Di l,u > k. The value cl,u is greater than k − u + l ≥ v + k − v − u + l ≥
v + k − u + l − v ≥ l − v as u ≤ v + k.

ut Observation 1 shows that it is sufficient to check intervals [v, v + k], {v, v + k} ∈
L∪U. We can infer all pruning from these intervals. Let [l, u], *l, u* ∈ L∪U be an interval that violates conditions (5)–(7) for a variable Xi and cl,u be the violation cost. Then we remove the interval [l − (cl,u − 1), u] from D(Xi), as any interval between [l − (cl,u −
1), u] and [*l, u*] is a violated interval. A dual observation holds for conditions (8)–(10).

This reduces the time complexity of checking (5)–(10) to O(n 3).

## 6 Faster Bounds Consistency Algorithm

Observation 1 allows us to construct a faster algorithm to enforce conditions (5)–(10).

First, we observe that the conditions can be checked for each variable independently.

Consider a variable Xi. We sort all variables Xj , j = 1*, . . . , n* in a non-decreasing