
## 5 Alternative Approaches 5.1 Arithmetic Constraint

Barbara Smith (personal communication) has proposed enforcing **~x <**m ~y on vectors of length n via the arithmetic constraint n x0 +. . . nxn−1 < ny0 +**. . . n**yn−1. This is similar to the transformation of a leximin fuzzy CSP into an equivalent MAX CSP [Schiex *et al.*, 1995]. BC on such a constraint is equivalent to GAC on the original multiset ordering constraint. However, such an arithmetic constraint is only feasible for small n. Further, most existing solvers will not enforce BC on such an arithmetic constraint, but will delay it until all but one of the variables are instantiated.

## 5.2 Decomposition

Multiset ordering is equivalent to the lex ordering the associated occurrence vectors. As we have efficient algorithms for constructing occurrence vectors (via the global cardinality constraint [R´egin, 1996]) and for lex ordering
[Frisch *et al.*, 2002], this might be an alternative approach.

However, as the following theorem shows, such a decomposition hinders constraint propagation. Also, the two global cardinality constraints in such a decomposition are more expensive to enforce than the algorithm presented here. We write gcc(**~x, ~ox**) for the global cardinality constraint that channels from a vector of variables ~x to the associated occurrence vector ~ox. Theorem 4 GAC(**~x <**m ~y) *is strictly stronger than simultaneously enforcing* GAC(gcc(~x, ~ox)), GAC(gcc(**~y, ~oy**))*, and* GAC( ~ox <lex ~oy).

Proof: Clearly it is as strong. To show strictness, consider ~x = h{1, 2}, {1, 2}, {2}, {2}i and ~y =
h{1, 2}, {1, 2}, {0, 1, 2}, {0, 1}i. The multiset ordering constraint is not GAC since 0 in y2 has no support but the decomposition is unable to determine this. QED.

Another approach is to use the sorted constraint in the Eclipse solver. This ensures that the values taken by one vector of variables are identical but in sorted order to the values taken by a second vector of variables. To post a multiset ordering constraint on two vectors, we can channel each into a sorted vector and lex order these. The above example demonstrates that such a decomposition again hinders propagation.

The sorting constraint is also more expensive to enforce.

## 6 Experimental Results

We designed some experiments to test three goals. First, is multiset ordering an effective method for dealing with row and/or column symmetry? Second, how does multiset ordering compare to lex ordering? Which one breaks more symmetry? Is a combined method, which multiset orders one dimension and lex orders the other one of the matrix, superior?

Third, does our GAC algorithm do more inference in practice than the decomposition? Similarly, is the algorithm more efficient in practice than its decomposition?

The symmetry breaking constraints we used are strict lex ordering on the columns (<lexC), on the rows (<lexR); multiset ordering on the rows (≤mR), (strict) multiset ordering on the columns (≤mC and <mC); and combinations of these

| Fails                | Choice points   | Time (secs.)   |      |
|----------------------|-----------------|----------------|------|
| No Symmetry Breaking | 180,738         | 180,860        | 75.9 |
| <lexC                | 180,738         | 180,860        | 81.5 |
| <lexR                | 2,720           | 2,842          | 2.7  |
| <lexRC               | 2,720           | 2,842          | 2.7  |
| ≤mC                  | 137,185         | 137,306        | 71.2 |
| ≤mR                  | 10,853          | 10,977         | 8.6  |
| ≤mRC                 | -               | -              | -    |
| <lexC ≤mR            | 10,853          | 10,977         | 8.6  |
| ≤mC <lexR            | 2,016           | 2,137          | 2.6  |

constraints. Such constraints are posted between adjacent rows/columns. The results of the experiments are shown in tables where a "-" means no result is obtained in 1 hour (3600 secs). The experiments are done using ILOG Solver 5.2 on a 1000MHz pentimum III with 256 Mb RAM.

## 6.1 Progressive Party Problem

There are a set of host boats, each with a capacity, and a set of guest boats, each with a crew size. We wish to assign a host for each guest and period, such that a guest crew never visits the same host twice, no two guest crews meet more than once, and the spare capacity of each host boat, after accommodating its own crew, is not exceeded (prob013 in csplib.org).

A matrix model of this problem [Smith *et al.*, 1995] is a 2-d matrix of guests × **periods** where each variable is assigned a host representing that a host is accommodating a particular guest in a given time period. The rows are the guests, the columns are the periods. This model has column and partial row symmetry: any two periods, and any two guests with the same crew size are indistinguishable. We consider the 13-hosts and 29 guests problem with 5 and 6 time periods, referred as 5-13-29 and 6-13-29. These problems have p!14!2!4!5!7! row and column symmetries where p is the number of time periods. The actual data can be found in csplib.org. Due to the problem constraints, no pair of rows/columns can be equal, hence we can safely pose strict lex ordering. However, any two distinct rows/columns might be equal when viewed as multisets.

As in [Smith *et al.*, 1995], the guest boats are ordered in descending order of their size. We order the host boats in descending order of spare capacity to choose a value in a succeed-first manner. Results obtained by row-by-row, and column-by-column labelling strategies are given in Tables 1 and 2. With row-by-row labelling, we cannot solve 6-13-29 with or without symmetry breaking. For the 5-13-29 problem,
<lexR breaks a lot more row symmetry than ≤mR. However, the reverse is true for the columns. Here, <lexC does not break any symmetry but ≤mC does. Multiset ordering one dimension of a matrix therefore does not necessarily break less symmetry than lex ordering the same dimension. Such phenomena occur through interactions with the search strategy: a search strategy might already lex order, so multiset ordering constraints break additional symmetry. The smallest search tree and also the least solving time is obtained by ≤mC
<lexR. This supports our conjecture that lex ordering one dimension combined with multiset ordering the other can break