

![0_image_1.png](0_image_1.png)

more symmetry than lex/multiset ordering both dimensions.

With column-by-column labelling, we are able to solve the 6-13-29 problem. Neither of <lexR, <lexC, <lexRC break any symmetry. The smallest search tree is obtained by ≤mC.

This supports our conjecture that multiset ordering one dimension can break more symmetry than lex ordering the same or both dimensions. If the search strategy already orders both dimensions lexicographically, imposing a constraint like multiset ordering in one dimension breaks additional symmetry.

## 6.2 Sports Scheduling With Odd Teams

This is a modified version of prob026 in csplib.org. We have n teams (n is odd), playing over n weeks. Each week is divided into (n − 1)/2 periods, and each period is divided into 2 slots, home and away. We wish to find a schedule so that every team plays at most once a week, every team plays twice in the same period over the tournament and every team plays every other team. We slightly modify the model in [Van Hentenryck *et al.*, 1999], where *teams* is a 3-d matrix of periods × weeks × **slots**. Each element of *teams* is the team playing in a given period, week and slot. We treat this matrix as 2-d where the rows are the periods and columns are the weeks, and each entry is a list of variables giving the slots.

As the periods and the weeks are indistinguishable, this problem has n!(n − 1/2)! row and column symmetries. We pose strict ordering constraints on the rows and columns of teams as the periods and weeks cannot be equal. Due to the constraints on the periods, posing multiset ordering on the rows is not effective.

Results obtained by column-by-column labelling of the teams are given in Table 3. For one column, we first label the first slots; for the other, we first label the second slots.

With this strategy, <lexR does not break any symmetry, so we omit it in the table. Posing multiset ordering by our algorithm is much more effective and efficient than by gcc and lex ordering constraints. This holds for many other search strategies. In Table 3, we note that <mC gives a smaller search tree than <lexC. However, for other search strategies the reverse is true. This supports the theoretical result that lex ordering and multiset ordering are incomparable.

## 7 Conclusions

We have identified a new and important global (non-binary)
constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. We have developed an efficient linear time algorithm

![0_image_0.png](0_image_0.png)

for enforcing generalised arc-consistency on such a multiset ordering constraint. We have proposed a number of applications for this new constraint including breaking symmetry in matrix models, and fuzzy constraint satisfaction. We have shown that alternative methods for posting a multiset ordering constraint like an arithmetic constraint or decomposition are inferior. Finally, we have implemented this generalized arcconsistency algorithm in ILOG Solver. Experimental results on a number of problem domains show considerable promise.

## References

[Beldiceanu, 2000] N. Beldiceanu. Global constraints as graph properties on a structured network of elementary constraints of the same type. In *Proc. of CP-2000*, LNCS 1894, pp 52–66, 2000.

[Fahle *et al.*, 2001] T. Fahle, S. Schamberger and M. Sellman. Symmetry Breaking. In *Proc. of CP-2001*, LNCS
2239, pp 93–107, 2001.

[Fargier, 1994] H. Fargier. Problemes de satisfaction de con- `
straintes flexibles: application a l'ordonnancement de pro- `
duction. PhD thesis, Uni. of Paul Sabatier, Toulouse, 1994.

[Flener *et al.*, 2002] P. Flener, A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson, and T. Walsh. Breaking row and column symmetry in matrix models. In *Proc. of CP-2002*,
LNCS 2470, pp 462–476, 2002.

[Frisch *et al.*, 2002] A. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh. Global constraints for lexicographic orderings. In *Proc. of CP-2002*, LNCS 2470, pp 93–108, 2002.

[Gent and Smith, 2000] I. Gent and B. Smith. Symmetry Breaking in Constraint Programming. In Proc. of ECAI '2000, pp 599–603, 2000.

[Kiziltan and Smith, 2002] Z. Kiziltan and B. Smith. Symmetry breaking constraints for matrix models. In *Proc. of* 2nd Int. Workshop on Symmetry in Constraint Satisfaction Problems (SymCon-02), held alongside CP-2002, 2002.

[Kiziltan and Walsh, 2002] Z. Kiziltan and T. Walsh. Constraint Programming with Multisets. In Proc. of 2nd Int.

Workshop on Symmetry in Constraint Satisfaction Problems (SymCon-02), held alongside CP-2002, 2002.

[R´egin, 1994] J.C. R´egin. A filtering algorithm for constraints of difference in CSPs. In *Proc. AAAI'94*, pp 362–
367. 1994.