Clearly, this experiment is limited in its scope, first by the relatively small size of the instances, and second by the choices made for generating random **domains. However, we**
conclude that examples of inconsistent values not being detected by the decomposition appear to be rare.

## 7.2 Pruning Power And Efficiency Of **Range**

Contrary to the Roots constraint, we have a complete HC propagator for the **Range**
constraint. Thus, we do not need to assess the pruning power of our propagator. Nevertheless, it can be interesting to compare the pruning power and the efficiency of decomposing a global constraint using Range **or using another decomposition with simpler**
constraints.

The purpose of this subsection is to compare the decomposition of Uses using **Range**
constraints against a simple decomposition using more elementary constraints. We chose the Uses constraint because it is NP-hard to achieve GAC on the Uses **constraint (see**
Section 6.1.4) and there is no propagator available for this constraint in the literature. Furthermore, one of the time-tabling problems at the University of **Montpellier can easily**
be modelled as a CSP with Uses **constraints. We first compare the two decompositions**
of Uses (with or without Range**) in terms of run-time as well as pruning power on**
random CSPs. Then, we solve the problem of building the set of courses in the Master of Computer Science at the University of Montpellier with the two decompositions.

## 7.2.1 Random Csps

In order to isolate the effect of the Range **constraint from other modelling issues, we**
used the following protocol: we randomly generated instances of binary CSPs and we added Uses([X1, .., Xn], [Y1, .., Yn]) constraints. In all our experiments, we encode **Uses**
in two different ways:
[range]: by decomposing Uses using Range **as described in Section 6.1.4,**
[decomp]: by decomposing the Uses **constraint using primitive constraints as described**
next.

Uses([X1, .., Xn], [Y1, .., Yn**]) iff**
$i\in S\to X_{i}\in T\ \wedge\ j\in T\to\exists i\in S.X_{i}=j\wedge i\in S^{\prime}\to Y_{i}\in T^{\prime}\ \wedge\ j\in T^{\prime}\to\exists i\in S^{\prime}.Y_{i}=j\wedge i\in T\subseteq T^{\prime}$  $T\subseteq T^{\prime}$  $\bullet$\(\bullet
The problem instances are generated according to model B in [23], and can be described with the following parameters: the number of X and Y variables nx and ny in Uses constraints, the total number of variables nz, the domain size d**, the number of**
binary constraint m1, the number of forbidden tuples t **per binary constraint, and the**
number of Uses constraints m2. Note that the Uses **constraints can have overlapping**
or disjoint scopes of variables. We distinguish the two cases. All reported results are averages on 1000 instances.