The complexity of enforcing BC on the ATLEASTNVALUE constraint can be improved to O(nd2) in way similar to that described in Section 5 and in [6].

## 7 Experimental Results

To evaluate these decompositions, we performed experiments on two problem domains. We used the same problems as in a previous experimental comparison of propagators for the ATMOSTNVALUE constraint [5]. We ran experiments with Ilog Solver 6.2 on an Intel Xeon 4 CPU, 2.0 Ghz, 4Gb RAM.

## 7.1 Dominating Set Of The Queen'S Graph

The problem is to put the minimum number of queens on a n × n chessboard, so that each square either contains a queen or is attacked by one. This is equivalent to the dominating set problem of the Queen's graph. Each vertex in the Queen's graph corresponds to a square of the chessboard and there exists an edge between two vertices iff a queen from one square can attack a queen from the other square. To model the problem, we use a variable Xi for each square, and values from 1 to n 2and post a single ATMOSTNVALUE([X1, . . . , Xn2 ], N) constraint. The value j belongs to D(Xi)
iff there exists an edge (**i, j**) in the Queen's graph or j = i. We use minimum domain variable ordering and a lexicographical value ordering. For n ≤ 120, all minimum dominating sets for the Queen's problem are either of size ⌈n/2⌉ or ⌈n/**2 + 1**⌉ [10].

We therefore only solved instances for these two values of N.

We compare our decomposition with two simple decompositions of the ATMOSTNVALUE constraint. The first decomposition is the one described in Section 3.1 except that in constraint (3), we replace "=" by "≤". We denote this decomposition Occs. The second decomposition is similar to the first one, but we use the cardinality variables of a GCC constraint to keep track of the used values. We call this decomposition Occsgcc. The final two decompositions are variants of the decomposition described in Section 4, which we call P yramidBC or **P yramid**RC depending whether we enforce BC or RC on our decomposition. As explained in Section 5, we channel the variables Xi directly to the pyramid variables Mlu to avoid introducing many auxiliary variables Ailu and we add the redundant constraint Pn 2 i=1 Mii = M1,n2 to the decomposition to speed up the propagation across the pyramid. For the decomposition that enforces RC, we did not fully implement the O(nd2) decomposition of Section 5, but rather a simple channeling propagator that achieves RC in O(nd3) on (4), but with better asymptotic constants than constraints (4). Finally, we re-implemented the ternary sum constraint Z = X + Y in Ilog. This gave us about 30% speed up.

Results are presented in Table 1. Our decomposition performs better than the other two decompositions, both in runtime and in number of backtracks. We observe that BC and RC prune the same (i.e., same number of backtracks) on our decomposition but BC
is faster on larger problems. It should be pointed out that our results are comparable with the results for the ATMOSTNVALUE bounds consistency propagator from [5]. Whilst our decomposition is not as efficient as the best results presented in that paper, our decomposition was easier to implement.