
## 7 Experimental Results

We now experimentally assess the value of using the Range and Roots **constraints**
in specifying global counting and occurrence constraints. For these experiments, we implemented an algorithm achieving HC on Range **and an algorithm achieving HC on** the decomposition of Roots **presented in Section 5.2. Note that our algorithm for the**
decomposition of Roots does not **use the Ilog Solver primitives** member(value, set**) and** notmember(value, set**) because Ilog Solver does not appear to give complete propagation**
on combinations of such primitives (see the discussion in Section 5.5). **We therefore**
implemented our own algorithms from scratch.

## 7.1 Pruning Power Of **Roots**

In Section 5.2 we proposed a decomposition of the Roots **constraint into simple implications. The purpose of this subsection is to measure the pruning power of HC on the**
decomposition of Roots with respect to HC on the original Roots **constraint when we**
do not meet any of the conditions that make HC on the decomposition **equivalent to HC**
on the original constraint (see Section 5.3). We should bear in mind that enforcing HC
on the Roots constraint is NP-hard in general. In order to enforce HC on the **Roots**
constraint we used a simple table constraint (i.e., a constraint in extension) that has an exponential time and space complexity. Consequently, the size of the instances on which we were able to run this filtering method was severely constrained.

An instance is a set of integer variables {X1, ..Xn} and two set variables S and T .

It can be described by a tuple hn, m, k, ri. The parameter n **stands for the number of** integer variables. These n variables are initialised with the domain {1, . . . , m}**. The** upper bound of S is initialised with {1, . . . , n} and the upper bound of T **is initialised** with {1, . . . , m}. The parameter k **corresponds to the number of elements of the set**
variable S (resp. set variable T **) that are, with equal probability, either put in the lower**
bound or excluded from the upper bound of S (resp. of T **). Finally, the parameter** r is the total number of values removed, with uniform probabilities from the domains of the integer variables, keeping at least one value per domain. We generated 1000 random instances for each combination of n, m ∈ [4, ..6], k ∈ [1..min(n, m)] and r ∈ [1..n(m−**1)].**
For each one of the instances we generated, we propagated Roots([X1, ..Xn]**, S, T** )
using either the table constraint (enforcing HC), or our decomposition (enforcing HC in special cases). We observed that on 29 out of the 32 combinations **of the parameters** n, m and k, the decomposition achieves HC for all 1000 instances of every value of r**. On**
the remaining three classes (h4, 6, 3, ∗i, h5, 6, 3, ∗i and h6, 6, 3, ∗i**), the decomposition fails**
to detect 0.**003% of the inconsistent values.**
As a second experiment, we used the same instances expect that we did not fix or remove k values randomly from T , that is, in all instances, lb(T ) = ∅ and ub(T ) = {1, . . . , m}**. All other settings remained equal. By doing so, we allowed the random**
domains to reach situations equivalent to that of the counter example given in the proof of Theorem 4. With this setting, we observed that the decomposition still achieves HC on 18 out of the 32 combinations of the parameters n, m and k**, for all 1000 instances**
of every value of r**. On the remaining classes, the percentage of inconsistent values not** pruned by the decomposition increases to 0.**039%.**