Abstract
A global cardinality constraint (gcc) is specified in terms of a set of variables X={x 1,...,x p } which take their values in a subset of V={v 1,...,v d }. It constrains the number of times each value v i ∈ 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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice Hall, Englewood Cliffs (1993)
Beldiceanu, N., Contejean, E.: Introducing global constraints in chip. Journal of Mathematical and Computer Modelling 20(12), 97–123 (1994)
Caseau, Y., Guillo, P.-Y., Levenez, E.: A deductive and object-oriented approach to a complex scheduling problem. In: Ceri, S., Tsur, S., Tanaka, K. (eds.) DOOD 1993. LNCS, vol. 760, Springer, Heidelberg (1993)
Caseau, Y., Laburthe, F.: Solving various weighted matching problems with constraints. In: Proceedings CP 1997, Austria, pp. 17–31 (1997)
Cherkassky, B., Goldberg, A., Radzik, T.: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73, 129–174 (1996)
Laurière, J.-L.: A language and a program for stating and solving combinatorial problems. Artificial Intelligence 10, 29–127 (1978)
Puget, J.-F.: Personal communication (1999)
Régin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings AAAI 1994, Seattle, Washington, pp. 362–367 (1994)
Régin, J.-C.: Generalized arc consistency for global cardinality constraint. In: Proceedings AAAI 1996, Portland, Oregon, pp. 209–215 (1996)
Régin, J.-C.: Arc consistency for global cardinality constraints with costs. Technical report, ILOG Optimization Internal Report OIR-1999-2 (1999)
Tarjan, R.: Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics (1983)
Van Hentenryck, P., Deville, Y., Teng, C.: A generic arc-consistency algorithm and its specializations. Artificial Intelligence 57, 291–321 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Régin, JC. (1999). Arc Consistency for Global Cardinality Constraints with Costs. In: Jaffar, J. (eds) Principles and Practice of Constraint Programming – CP’99. CP 1999. Lecture Notes in Computer Science, vol 1713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48085-3_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-48085-3_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66626-4
Online ISBN: 978-3-540-48085-3
eBook Packages: Springer Book Archive