AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Decompositions of all Different, Global Cardinality and Related Constraints
Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Toby Walsh

Last modified: 2009-06-24


We show that some common and important global constraints like ALLDIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.


Global constraints; decompositions; encodings; constraint propagation

Full Text: PDF