Pn 2 i=1 Mii = M1,n2 to the decomposition to speed up the propagation across the pyramid. We re-implemented the ternary sum constraint in Ilog for a 30% speedup.

To encode the BC decomposition into an integer linear program, we use the linear encoding of variables domains [16]. We introduce literals cij for the truth of Xi ≤ j, and the channeling inequalities of the form ci(l−1) + 1 − ciu + Mlu ≥ 1. We again add the redundant constraint Pn 2 i=1 Mii = M1,n2 . Finally, we post constraints (6) as lazy constraints in CLPEX. Lazy constraints are constraints that are not expected to be violated when they are omitted. These constraints are not taken into account in the relaxation of the problem and are only included when they violate an integral solution.

| n N        | Occs            | P yramidBC      | OccsCP LEX      | P yramidCP LEX BC   |    |       |     |     |
|------------|-----------------|-----------------|-----------------|---------------------|----|-------|-----|-----|
| backtracks | time backtracks | time backtracks | time backtracks | time                |    |       |     |     |
| 5 3        | 34              | 0.01            | 7               | 0.00                | 1  | 0.05  | 3   | 0.4 |
| 6 3        | 540             | 0.16            | 118             | 0.03                | 2  | 0.16  | 183 | 9.6 |
| 7 4        | 195,212         | 84.50           | 83,731 15.49    | 130,010 1802.49     | 63 | 15.8  |     |     |
| 8 5        | 390,717 255.64  | 256,582 58.42   | 24,588          | 585.07              | 30 | 41.28 |     |     |

Table 1. Backtracks and rumtime (in seconds) to solve the dominating set problem for the Queen's graph.

Results of our experiments are presented in Table 1. Our BC decomposition performs better than the **Occs** decomposition, both in runtime and in number of backtracks needed by Ilog Solver or CPLEX. CPLEX is slower per node than Ilog Solver.

However, CPLEX usually requires fewer backtracks compared to ILOG Solver. Interestingly CPLEX performs well with the BC decomposition. The time to explore each node is large, reflecting the size of decomposition, but the number of search nodes explored is small. We conjecture that integer linear programming methods like CPLEX will perform in a similar way with other decompositions of global constraints which do not hinder propagation (e.g. the decompositions we have proposed for ALL-DIFFERENT and GCC). Finally, the best results here are comparable with those for the ATMOSTNVALUE bounds consistency propagator in [13].

## 8 Other Related Work

Bessiere *et al.* consider a number of different methods to compute a lower bound on the number of values used by a set of variables [13]. One method is based on a simple linear relaxation of the minimum hitting set problem. This gives a propagation algorithm that achieves a level of consistency strictly stronger than bound consistency on the NVALUE constraint. Cheaper approximations are also proposed based on greedy heuristics and an approximation for the independence number of the interval graph due to Tur´an. Decompositions have been given for a number of other global constraints. For example, Beldiceanu *et al.* identify conditions under which global constraints specified as automata can be decomposed into signature and transition constraints without hindering