Abstract
We propose two algorithms achieving generalized arc consistency for the soft global cardinality constraint with variable-based violation and with value-based violation. They are based on graph theory and their complexity is \(O(\sqrt{n}m)\) where n is the number of variables and m is the sum of the cardinalities of the domains. They improve previous algorithms that ran respectively in O(n(m+nlog n)) and O((n+k)(m+nlog n)) where k is the cardinality of the union of the domains.
This is a preview of subscription content, log in via an institution to check access.
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.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs (1993)
Dubois, D., Fargier, H., Prade, H.: The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In: Proceedings of the Second IEEE International Conference on Fuzzy Systems, vol. 2, pp. 1131–1136 (1993)
Fargier, H., Lang, J., Schiex, T.: Selecting preferred solutions in fuzzy constraint satisfaction problems. In: Proceedings of the First European Congress on Fuzzy and Intelligent Technologies (EUFIT 1993), Aachen, vol. 3, pp. 1128–1134 (1993)
van Hoeve, W.J., Pesant, G., Rousseau, L.M.: On Global Warming: Flow-Based Soft Global Constraints. Journal of Heuristics (to appear)
Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2(4), 225–231 (1973)
Larrosa, J.: Node and Arc Consistency in Weighted CSP. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence, pp. 48–53. AAAI Press, Menlo Park (2002)
Larrosa, J., Schiex, T.: In the Quest of the best form of local consistency for Weighted CSP. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, pp. 239–244. Morgan Kaufmann, San Francisco (2003)
Quimper, C.-G., López-Ortiz, A., van Beek, P., Golynski, A.: Improved Algorithms for the Global Cardinality Constraint. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 542–556. Springer, Heidelberg (2004)
Petit, T., Régin, J.-C., Bessière, C.: Specific Filtering Algorithms for Over Constrained Problems. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 451–463. Springer, Heidelberg (2001)
Régin, J.-C.: Arc Consistency for Global Cardinality Constraints with Costs. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 390–404. Springer, Heidelberg (1999)
Régin, J.-C.: Generalized Arc Consistency for Global Cardinality Constraint. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI 1996), pp. 209–215 (1996)
Schiex, T.: Possibilistic Constraint Satisfaction Problems or “How to handle soft constraints?”. In: Proceedings of the 8th Annual Conference on Uncertainty in Artificial Intelligence, pp. 268–275. Morgan Kaufmann, San Francisco (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zanarini, A., Milano, M., Pesant, G. (2006). Improved Algorithm for the Soft Global Cardinality Constraint. In: Beck, J.C., Smith, B.M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2006. Lecture Notes in Computer Science, vol 3990. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11757375_23
Download citation
DOI: https://doi.org/10.1007/11757375_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34306-6
Online ISBN: 978-3-540-34307-3
eBook Packages: Computer ScienceComputer Science (R0)