Decomposition. Consider any ALLDIFFERENT constraint. A subset of n or fewer variables has at least 2n − 1 values in their domains and a subset of n+ 1 to 3n variables has 4n−1 values in their domains. Thus, to obtain a Hall set and prune, we must instantiate at least n − 1 variables.

## Experimental Results

To evaluate the performance of our decomposition we carried out an experiment on random problems. We used Ilog 6.2 on an Intel Xeon 4 CPU, 2.0 GHz, 4GB RAM.

We compare the performance of the DC, BC (LopezOrtiz *et al.* 2003) propagators and our decomposition into constraints (3)-(12) for the OVERLAPPINGALLDIFF
constraint (OBC). We use randomly generated problems with three global constraints: ALLDIFFERENT(X ∪ W),
ALLDIFFERENT(Y ∪W) and ALLDIFFERENT(Z∪W), and a linear number of binary ordering relations between variables in X, Y and Z. We use a random variable ordering and run each instance with 50 different seeds. As Table 1 shows, our decomposition reduces the search space significantly, is much faster and solves more instances overall.

Table 1: Random problems. n is the size of X, Y and Z,
o is the size of W, d is the size of variable domains. Number of instances solved in 300 sec out of 50 runs / average backtracks/average time to solve.

| n,d,o            | BC                 | DC                  | OBC               |
|------------------|--------------------|---------------------|-------------------|
| #s / #bt / t     | #s / #bt / t       | #s / #bt / t        |                   |
| 4, 15, 10        | 14 /2429411 / 61.8 | 41 /1491341 / 52.1  | 42 / 17240 / 32.5 |
| 4, 16, 11        | 6 /5531047 / 153.7 | 22 /1745160 / 67.9  | 31 / 8421 / 19.5  |
| 4, 17, 12        | 1 / 17 / 0         | 6 /2590427 / 100.9  | 24 / 8185 / 21.5  |
| 5, 16, 10        | 11 /3052298 / 82.0 | 37 /1434903 / 58.2  | 42 / 20482 / 48.5 |
| 5, 17, 11        | 2 /3309113 / 94.5  | 19 /2593819 / 114.6 | 26 / 4374 / 15.8  |
| 5, 18, 12        | 1 / 17 / 0         | 4 /2666556 / 133.1  | 22 / 3132 / 12.2  |
| 6, 17, 10        | 11 /2845367 / 79.1 | 31 /1431671 / 66.3  | 40 / 6796 / 21.9  |
| 6, 18, 11        | 4 / 199357 / 6.6   | 16 /1498128 / 80.2  | 31 / 4494 / 17.5  |
| 6, 19, 12        | 4 /3183496 / 110.0 | 5 /1035126 / 66.2   | 27 / 3302 / 15.5  |
| TOTALS sol/total | 54 /450            | 181 /450            | 285 /450          |
| avg time for sol | 78.072             | 70.551              | 24.689            |
| avg bt for sol   | 2818926            | 1666568             | 9561              |

## Conclusions

We have generalized Hall's theorem to simultaneous matchings in a bipartite graph. This generalization suggests a polynomial time algorithm to find a simultaneous matching in a convex bipartite graph. We applied this to a problem in constraint programming of propagating conjunctions of ALLDIFFERENT constraints. Initial experimental results suggest that reasoning about such conjunctions can significantly reduce the size of the explored search space. There are several avenues for future research. For example, the algorithmic techniques proposed in (Puget 1998) and (LopezOrtiz *et al.* 2003) may be generalizable to simultaneous bipartite matchings, giving more efficient propagators. Further, matchings are used to propagate other constraints such as NVALUE (Bessiere *et al.* 2006). It may be possible to apply similar insights to develop propagators for conjunctions of other global constraints, or to improve existing propagators for global constraints that decompose into overlapping constraints like SEQUENCE (Brand *et al.* 2005). Finally, we may be able to develop polynomial time propagators for otherwise intractable cases if certain parameters are fixed
(Bessiere *et al.* 2008).

## Acknowledgments

This research is supported by ANR UNLOC project (ANR
08-BLAN-0289-01), the Australian Government's Department of Broadband, Communications and the Digital Economy and the ARC.

## References

[Bessiere *et al.* 2006] Bessiere, C.; Hebrard, E.; Hnich, B.;
Kiziltan, Z.; and Walsh, T. 2006. Filtering algorithms for the NVALUE constraint. *Constraints*, 11 (4): 271–293.

[Bessiere *et al.* 2008] Bessiere, C.; Hebrard, E.; Hnich, B.;
Kiziltan, Z.; and Walsh, T. 2008. The Parameterized Complexity of Global Constraints. In *Proc. of 23rd AAAI*, 235–
240.

[Bessiere *et al.* 2007] Bessiere, C.; Hebrard, E.; Hnich, B.;
and Walsh, T. 2007. The Complexity of Reasoning with Global Constraints. *Constraints.* 12(2): 239–259.

[Bessiere *et al.* 2009] Bessiere, C.; Katsirelos, G.; Narodytska, N.; Quimper, C.-G.; and Walsh, T. 2009. Decompositions of all different, global cardinality and related constraint. In *Proc. of 21st IJCAI*, 419–424.

[Brand *et al.* 2005] Brand, S.; Narodytska, N.; Quimper, C.-
G.; Stuckey, P.; and Walsh, T. 2007. Encodings of the Sequence Constraint. In *Proc. of CP-2007*, 210–224.

[Diestel 2006] Diestel, R. 2006. *Graph Theory*. Springer.

[Hall 1935] Hall, P. 1935. On representatives of subsets. J.

of the London Math. Soc. 10:26–30.

[Kutz *et al.* 2008] Kutz, M.; Elbassioni, K.; Katriel, I.; and Mahajan, M. 2008. Simultaneous matchings: Hardness and approximation. *J. of Computer and System Sciences* 74(5):884–897.

[Lardeux *et al.* 2008] Lardeux, F.; Monfroy, E.; and Saubion, F. 2008. Interleaved Alldifferent Constraints: CSP vs. SAT
Approaches. In *Proc. of AIMSA*, 380-384.

[Lauriere 1978] Lauri ` ere, J.-L. 1978. A language and a pro- `
gram for stating and solving combinatorial problems. *Art.*
Intell.10:29–127.

[Leconte 1996] Leconte, M. 1996. A bounds-based reduction scheme for constraints of difference. In Proc. of 2nd Int.

Workshop on Constraint-based Reasoning.

[Lopez-Ortiz *et al.* 2003] Lopez-Ortiz, A.; Quimper, C.;
Tromp, J.; and van Beek, P. 2003. A fast and simple algorithm for bounds consistency of the alldifferent constraint.

Proc. of 18th IJCAI, 245–250.

[Puget 1998] Puget, J. 1998. A fast algorithm for the bound consistency of alldiff constraints. In *15th Nat. Conf. on AI*,
359–366.