Instead of trying to satisfy only one of their choices, we try now to satisfy k **choices. The**
models are modified in the following way. We create k copies of each variable Sj **, that**
is, S
1 j
, S2 j
, . . . , Sk j
, with D(S
i j
) containing the same values as D(Sj **) (see above). We post**
constraints S
1 j < S2 j **< . . . < S**k j that break symmetries and guarantee that S
1 j
, S2 j
, . . . , Sk j all take different values. Then, instead of having a single Uses constraint, we have k **Uses**
constraints, one on each set S
i 1
, Si2
, . . . , Sim of variables: Uses([L1**, . . . , L**n], [S
1 1
, . . . , S1m]),
. . ., Uses([L1**, . . . , L**n], [S
k 1, . . . , Skm**]). Model** range-k decomposes Uses with **Range**,
and model decomp-k decomposes Uses **with primitive constraints as described in Section**
7.2.1.

We solved instance year-2008 with k = 2, 3, 4, 5. When k = 2 or k **= 3, both models**
find a solution in a few milliseconds, decomp-k **being slightly faster than** range-k.

range**-4 finds a solution in 4 fails and 5.83 sec. whereas** decomp**-4 was stopped after 24** hours without finding any solution. range**-5 and** decomp**-5 were stopped after 24 hours**
without finding any solution or proving that none exists. This experiment shows that it can be effective to solve a real-world problem containing a global constraint like **Uses** by specifying it with Range **instead of using a decomposition with elementary constraints.**

## 7.3 Solving Problems Using Range And **Roots**

In Section 7.2.2, we showed how decomposing a global constraint with Range **can be**
useful to solve a real-world problem. In this subsection we study another real-world problem that involves a greater variety of global constraints, some allowing decompositions with Range, some others with Roots**. More importantly, we will compare monolithic**
propagators of existing well-known global constraints with their decompositions using Range and Roots. The purpose of this subsection is to see if solving real-world constraint problems using Range and Roots **leads to acceptable performance compared to**
specialised global constraints and their propagators.

We used a model for the Mystery Shopper problem [16] due to Helmut Simonis that appears in CSPLib (prob004). We used the same problem instances as in [10] but perform a more thorough and extensive analysis. We partition the constraints of this problem into three groups:
Temporal and geographical: **All visits for any week are made by different shoppers.**
Similarly, a particular area cannot be visited more than once by the same shopper.

Shopper: **Each shopper makes exactly the required number of visits.**
Saleslady: A saleslady must be visited by some shoppers from at least 2 different **groups**
(the shoppers are partitioned into groups).

The first group of constraints can be modelled by using AllDifferent **constraints**
[25], the second can be modelled by Gcc [26] and the third by Among **constraints [4]. We**
experimented with several models using Ilog Solver where these constraints are either implemented as their Ilog Solver primitives (respectively, IloAllDiff, IloDistribute, and a decomposition using IloSum **on Boolean variables) or as their decompositions with**
Range and Roots. The decomposition of Among([X1, .., Xn], [d1, .., dm], N**) we use is**
the one presented in [6], that is, (Bi = 1 ↔ Xi ∈ [d1, .., dm]), ∀i ∈ 1..n∧Pi Bi = N**. Note**
that this decomposition of the Among **constraint maintains GAC in theory [6]. This**