
| alld-gcc-sum-lex   | alld-roots-roots-set   |             |        |         |             |         |        |       |         |         |
|--------------------|------------------------|-------------|--------|---------|-------------|---------|--------|-------|---------|---------|
| 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        | 10      | 0.05   | 0.05  | 98.20   | 91.33   |
| 15                 | 29                     | 0.07        | 0.07   | 431.55  | 431.55      | 52      | 0.12   | 0.05  | 102.83  | 23.34   |
| 20                 | 25                     | 0.02        | 0.02   | 10.60   | 10.60       | 35      | 1.30   | 1.25  | 852.14  | 794.20  |
| 25                 | 16                     | 0.03        | 0.03   | 7.06    | 7.06        | 20      | 5.08   | 5.12  | 2218.00 | 2170.12 |
| 30                 | 6                      | 0.05        | 0.05   | 50.00   | 50.00       | 10      | 15.05  | 3.65  | 4476.40 | 1675.33 |
| 35                 | 31                     | 0.23        | 0.23   | 414.68  | 412.24      | 51      | 33.88  | 35.86 | 6111.67 | 6410.14 |

## 7.3.4 Exploiting The Set Variables

In the previous subsections, we have seen that decomposing global constraints with Range and Roots **constraints is a viable approach. Such decompositions generally**
give very small (if any) loss in terms of pruning and they give acceptable run-time performance. However, we have seen that our basic decomposition using Roots **can be slow**
compared to highly specialised propagators such as those used by Ilog Solver for the Gcc constraint. In this subsection, we show that, even without optimising our code, we can improve the run-time performance of our decomposition just by exploiting its internal structure through the extra variables it introduces.

The decomposition of global constraints using Range and Roots **introduces extra**
set variables. We here explore the possibility of branching on the set **variables as follows.**
We branch on the set variables first, then on the integer variables with min domain once all set variables are instantiated. We refer to this as set**. We compare the best model that**
uses the available constraints in Ilog Solver (model Alld-Gcc-Sum**) versus the best model**
that branches on the set variables (model Alld-Roots-Roots, in which the **Among** and the Gcc constraints are expressed using the Roots **constraint). Surprisingly, we**
solve significantly more instances when branching on the set variables than the model Alld-Gcc-Sum**. But, again,** Alld-Gcc-Sum **is a more efficient model when it manages**
to solve the instance.

These results are primarily due to the better branching strategy. **However, such a**
strategy would not be easily implementable without Roots **since the extra set variables** are part of it. We observe here that the extra set variables introduced by the **Roots**
decomposition may provide new possibilities for branching strategies **that might be beneficial in practice.**
These results show that by simply changing the branching strategy **so that it exploits**
the internal structure of the decompositions, we obtain a significant increase in performance. This gain compensates the loss in cpu-time caused by the preliminary nature of our implementation.

## 8 Conclusion

We have proposed two global constraints useful in specifying many counting and occurrence constraints: the Range **constraint which computes the range of values used**
by a set of variables, and the Roots **constraint which computes the variables in a set**