(PDF) Claude-Guy Quimper, Peter van Beek, Alejandro Lopez-Ortiz, Alexander Golynski, and Sayyed Bashir Sadjad. An efficient bounds consistency algorithm for the global cardinality constraint. Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming, Kinsale, Ireland, 600-614, September, 2003. A longer technical report version is available.
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.
An implementation of the algorithm for bounds consistency propagation of the generalized cardinality constraint presented in the paper: README, gcc.tar.gz
Also included are some example benchmark and random problems that use the alldifferent constraint.
Note: All of the code relies on the ILOG Solver Library.