Generalized Arc Consistency for Global Cardinality Constraint

A global cardinality constraint (gee) is specified in terms of a set of variables X = { 21, .. ., zP} which take their values in a subset of V = { 01, .. ., vd}. It constrains the number of times a value V; 6 V is assigned to a variable in X to be in an interval [I; , ~1. Cardinality constraints have proved very useful in many real-life problems, such as scheduling, timetabling, or resource allocation. A gee is more general than a constraint of difference, which requires each interval to be [0, 11. In this p p a er, we present an efficient way of implementing generalized arc consistency for a gee. The algorithm we propose is based on a new theorem of flow theory. Its space complexity is 0(1X1 x IVl) and its time complexity is 0( 1x1” x IV/). We also show how this algorithm can efficiently be combined with other filtering techniques.

Authors

• Jean-Charles Régin Université Côte d'Azur

Keywords

No keywords are indexed for this paper.