Abstract
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications, 1st Edition. Prentice Hall.
Caseau, Y., Guillo, P.-Y., & Levenez, E. (1993). A deductive and object-oriented approach to a complex scheduling problem. In Deductive and Object-Oriented Databases, pages 67–80.
Gabow, H. N., & Tarjan, R. E. (1983). A linear-time algorithm for a special case of disjoint set union. In Proceedings of the Fifteenth ACM Symposium on Theory of Computing, pages 246–251.
Hall, P. (1935). On representatives of subsets. J. Lond. Math. Soc. 26–30.
Hopcroft, J., & Karp, R. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2: 225–231.
ILOG S. A. (1998). ILOG Solver 4.2 user’s manual.
Katriel, I., & Thiel, S. (2003). Fast bound consistency for the global cardinality constraint. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming, Kinsale, Ireland, pages 437–451.
Lipski, W., & Preparata, F. P. (1981). Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15: 329–346.
López-Ortiz, A., Quimper, C.-G., Tromp, J., & van Beek, P. (2003). A fast and simple algorithm for bounds consistency of the alldifferent constraint. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, pages 245–250.
Puget, J.-F. (1998). A fast algorithm for the bound consistency of alldiff constraints. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, Madison, Wisconsin, pages 359–366.
Quimper, C.-G., López-Ortiz, A., van Beek, P., & Golynski, A. (2004). Improved algorithms for the global cardinality constraint. In Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, Toronto, Ontario, pages 542–556 (September).
Régin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of the Twelfth National Conference on Artificial Intelligence, Seattle, pages 362–367.
Régin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, Oregon, pages 209–215.
Régin, J.-C., & Puget, J.-F. (1997). A filtering algorithm for global sequencing constraints. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, Linz, Austria, pages 32–46.
Schulte, C., & Stuckey, P. J. (2001). When do bounds and domain propagation lead to the same search space. In Proceedings of the Third International Conference on Principles and Practice of Declarative Programming, Firenze, Italy, pages 115–126.
Stergiou, K., & Walsh, T. (1999). The difference all-difference makes. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, Stockholm, pages 414–419.
Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM J. Comput. 1: 146–160.
van Beek, P., & Wilken, K. (2001). Fast optimal instruction scheduling for single-issue processors with arbitrary latencies. In Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming, Paphos, Cyprus, pages 625–639.
Van Hentenryck, P., Michel, L., Perron, L., & Régin, J.-C. (1999). Constraint programming in OPL. In Proceedings of the First International Conference on Principles and Practice of Declarative Programming, Paris, pages 98–116.
Van Hentenryck, P., Simonis, H., & Dincbas, M. (1992) Constraint satisfaction using constraint logic programming. Artif. Intell. 58: 113–159.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Quimper, CG., Golynski, A., López-Ortiz, A. et al. An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint. Constraints 10, 115–135 (2005). https://doi.org/10.1007/s10601-005-0552-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-005-0552-y