
| alld-gcc-sum-lex   | alld-gcc-roots-lex   |             |        |         |             |         |        |      |        |        |
|--------------------|----------------------|-------------|--------|---------|-------------|---------|--------|------|--------|--------|
| Size               | #solved              | time (sec.) | #fails | #solved | time (sec.) | #fails  |        |      |        |        |
| by self            | by all               | by self     | by all | by self | by all      | by self | by all |      |        |        |
| 10                 | 9                    | 0.01        | 0.01   | 0.89    | 0.89        | 9       | 0.01   | 0.01 | 0.89   | 0.89   |
| 15                 | 29                   | 0.07        | 0.07   | 431.55  | 431.55      | 29      | 0.07   | 0.07 | 281.90 | 281.90 |
| 20                 | 25                   | 0.02        | 0.02   | 10.60   | 10.60       | 25      | 0.02   | 0.02 | 9.48   | 9.48   |
| 25                 | 16                   | 0.03        | 0.03   | 7.06    | 7.06        | 16      | 0.04   | 0.04 | 7.00   | 7.00   |
| 30                 | 6                    | 0.05        | 0.05   | 50.00   | 50.00       | 6       | 0.07   | 0.07 | 49.67  | 49.67  |
| 35                 | 31                   | 0.23        | 0.23   | 414.68  | 414.68      | 31      | 0.24   | 0.24 | 269.32 | 269.32 |

- **We branch on the variables with the minimum domain first and assign values**
lexicographically. We refer to this as dom;

- **We assign a shopper to each saleslady for the first, then for the second week and**
so on. This a static variables and value ordering heuristic. We refer to this as lex.
However, since lex was consistently better than dom **we only report the results using**
lex.

All instances solved in the experiments use a time limit of 5 minutes. For **each class**
of instances we report the number of instances solved (\#solved**), the average cpu-time** in seconds over all instances solved by the method (by self**), the average cpu-time in**
seconds over all instances solved by both methods (by all**), the average number of failures** over all instances solved by the method (by self**), the average number of failures over** all instances solved by both methods (**by all**).

## 7.3.1 Among

When branching on the integer variables using lex **(Table 1) strategy, the** Alld-Gcc-Roots **model tends to perform better than the** Alld-Gcc-Sum **model in terms of pruning**
(smaller number of fails). Note that the Sum decomposition misses some pruning because of the Ilog Solver propagators used in this decomposition, as explained at the beginning of Section 7.3. This explains the discrepancy. Both models solve the same number of instances. The results show that in this case of the Among constraint, our **Roots**
decomposition is as efficient as the decomposition using elementary Sum constraints.

Minor run-time differences are probably due to the cheaper propagator of Ilog Solver which achieves less pruning.

## 7.3.2 Gcc

The Gcc **constraint is one of the most efficient and effective global constraints available**
in most constraint toolkits. The results comparing the Alld-Gcc-Sum **model versus its**
equivalent (the Alld-**Roots**-Sum model) where instead of Gcc **constraints we use our**
decomposition using Roots **are shown in Table 2. We observe that when branching on**
the integer variables using lex**, the loss in terms of pruning due to our decomposition** is very low: the difference in number of fails is less than 5% on the hardest instances.

This means that our decomposition should scale well when size and difficulty of problems