# zbMATH — the first resource for mathematics

Cost-based arc consistency for global cardinality constraints. (English) Zbl 1028.68157
Summary: A global cardinality constraint (gcc) is specified in terms of a set of variables $$X=\{x_1,\cdots,x_p\}$$ which take their values in a subset of $$V=\{v_1,\cdots,v_d\}$$. It constrains the number of times each value $$v_i\in V$$ is assigned to a variable in $$X$$ to be in an interval $$[l_i,u_i]$$. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm.

##### MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: