An Efficient Bound Consistency Algorithm for the Global Cardinality Constraint Problem. Claude-Guy. Quimper, Peter van Beek, A. López-Ortiz, Alexander Golynski, and Samed B. Sadjad. In Proceedings of 9^th International Conference on Principles and Practice of Constraint Programming (CP), Lecture Notes in Computer Science 2833, Springer-Verlag, pp. 600-614, 2003  [Postscript file]

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 our bounds consistency algorithm is competitive with and 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.