
## 6.5 Applications Beyond Counting And Occurrence Constraints

The Range and Roots **constraints are useful for specifying a wide range of counting**
and occurrence constraints. Nevertheless, their expressive power permits their use to specify many other constraints.

## 6.5.1 Element

The Element **constraint introduced in [31] indexes into an array with a variable. More**
precisely, Element(I, [X1, .., Xn], J) holds iff XI = J**. For example, we can use such**
a constraint to look up the price of a component included in a configuration problem.

The Element constraint can be decomposed into a Range **constraint without hindering**
propagation:
Element(I, [X1, .., Xn], J) iff |S| = |T | = 1 ∧ I ∈ S ∧ J ∈ T ∧ Range([X1, .., Xn]**, S, T** )
Theorem 24 GAC on Element **is equivalent to HC on the decomposition.**
Proof: S has all the values in the domain of I in its upper bound. Similarly T **has all**
the values in the domain of J in its upper bound. In addition, S and T **are forced to**
take a single value. Thus enforcing HC on Range([X1, .., Xn], S, T **) has the same effect**
as enforcing GAC on Element(I, [X1, .., Xn], J). ✷

## 6.5.2 Global Contiguity

The Contiguity **constraint ensures that, in a sequence of 0/1 variables, those taking**
the value 1 appear contiguously. This is a discrete form of convexity. The constraint was introduced in [21] to model a hardware configuration problem. It can be decomposed into a Roots **constraint:**
Contiguity([X1, .., Xn**]) iff**
Roots([X1, .., Xn]**, S,** {1}) ∧
X = max(S) ∧ Y = min(S) ∧ |S| = X − Y + 1 Again it is polynomial to enforce HC on this case of the Roots **constraint. Unfortunately,** decomposition hinders propagation. Whilst Range and Roots **can specify concepts**
quite distant from counting and occurrences like convexity, it seems that we may need other algorithmic ideas to propagate them effectively.

Theorem 25 GAC on Contiguity **is stronger than HC on the decomposition.**
Proof: Consider X1, X3 ∈ {0, 1}, X2, X4 ∈ {1}. Hybrid consistency on the decomposition will enforce {2, 4} ⊆ S ⊆ {1, 2, 3, 4}, X ∈ {4}, Y ∈ {1, 2} and |S| **to be in** {3, 4}
but no pruning will happen. However, enforcing GAC on Contiguity([X1, .., Xn**]) will**
prune 0 from X3. ✷