- Claude-Guy Quimper5,
- Peter van Beek5,
- Alejandro López-Ortiz5,
- Alexander Golynski5 &
- …
- Sayyed Bashir Sadjad5
Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2833))
Included in the following conference series:
1212Accesses
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 thegcc. We also present a new algorithm for domain consistency propagation of thegcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
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
Caseau, Y., Guillo, P.-Y., Levenez, E.: A deductive and object-oriented approach to a complex scheduling problem. In: Deductive and Object-Oriented Databases, pp. 67–80 (1993)
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: STOC 1983, pp. 246–251 (1983)
Hall, P.: On representatives of subsets. J. of the London Mathematical Society, 26–30 (1935)
Ilog, S. A.: ILOG Solver 4.2 user’s manual (1998)
Katriel, I., Thiel, S.: Fast bound consistency for the global cardinality constraint. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 437–451. Springer, Heidelberg (2003)
Lipski, W., Preparata, F.P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15, 329–346 (1981)
López-Ortiz, C.-G., Quimper, J.T., van Beek, P.: A fast and simple algorithm for bounds consistency of the alldifferent constraint. In: IJCAI 2003 (2003)
Puget, J.-F.: A fast algorithm for the bound consistency of alldiff constraints. In: AAAI 1998, pp. 359–366 (1998)
Régin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: AAAI 1994, pp. 362–367 (1994)
Régin, J.-C.: Generalized arc consistency for global cardinality constraint. In: AAAI 1996, pp. 209–215 (1996)
Régin, J.-C., Puget, J.-F.: A filtering algorithm for global sequencing constraints. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 32–46. Springer, Heidelberg (1997)
Schulte, C., Stuckey, P.J.: When do bounds and domain propagation lead to the same search space. In: PPDP 2001, pp. 115–126 (2001)
Stergiou, K., Walsh, T.: The difference all-difference makes. In: IJCAI 1999, pp. 414–419 (1999)
van Beek, P., Wilken, K.: Fast optimal instruction scheduling for single-issue processors with arbitrary latencies. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 625–639. Springer, Heidelberg (2001)
Van Hentenryck, P., Michel, L., Perron, L., Régin, J.-C.: Constraint programming in OPL. In: Nadathur, G. (ed.) PPDP 1999. LNCS, vol. 1702, pp. 98–116. Springer, Heidelberg (1999)
Van Hentenryck, P., Simonis, H., Dincbas, M.: Constraint satisfaction using constraint logic programming. Artificial Intelligence 58, 113–159 (1992)
van Hoeve, W.J.: The alldifferent constraint: A survey (2001) unpublished manuscript
Author information
Authors and Affiliations
School of Computer Science, University of Waterloo, Waterloo, Canada
Claude-Guy Quimper, Peter van Beek, Alejandro López-Ortiz, Alexander Golynski & Sayyed Bashir Sadjad
- Claude-Guy Quimper
You can also search for this author inPubMed Google Scholar
- Peter van Beek
You can also search for this author inPubMed Google Scholar
- Alejandro López-Ortiz
You can also search for this author inPubMed Google Scholar
- Alexander Golynski
You can also search for this author inPubMed Google Scholar
- Sayyed Bashir Sadjad
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Trieste 63, 35121, Padova, Italy
Francesca Rossi
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Quimper, CG., van Beek, P., López-Ortiz, A., Golynski, A., Sadjad, S.B. (2003). An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_41
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-20202-8
Online ISBN:978-3-540-45193-8
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative