Abstract
The paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One practical interest of the paper is to describe an implementation of the number of distinct values constraint. This is a quite common counting constraint that one encounters in many practical applications such as timetabling or frequency allocation problems. A second important contribution is to provide a pruning algorithm for the constraint “at most n distinct values for a set of variables”. This can be considered as the counterpart of Regin's algorithm for the all different constraint where one enforces having at least n distinct values for a given set of n variables.
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
Beldiceanu, N.: Global Constraints as Graph Properties on Structured Network of Elementary Constraints of the Same Type. SICS Technical Report T2000/01, (2000).
Cormen, T. H., Leiserson, C. E., Rivest R. L.: Introduction to Algorithms. The MIT Press, (1990).
Costa, M-C.: Persistency in maximum cardinality bipartite matchings. Operation Research Letters 15, 143–149, (1994).
Damaschke, P., Müller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Information Processing Letters 36, 231–236, (1990).
Garey, M. R., Johnson, D. S.: Computers and intractability. A guide to the Theory of NP-Completeness. W. H. Freeman and Company, (1979).
Pachet, F., Roy, P.: Automatic Generation of Music Programs. In Principles and Practice of Constraint Programming-CP’99, 5th International Conference, Alexandria, Virginia, USA, (October 11-14, 1999), Proceedings. Lecture Notes in Computer Science, Vol. 1713, Springer, (1999).
Règin, J-C.: A filtering algorithm for constraints of difference in CSP. In Proc. of the Twelfth National Conference on Artificial Intelligence (AAAI-94), 362–367, (1994).
Règin, J-C.: Développement d’outils algorithmiques pour l’Intelligence Artificielle. Application á la chimie organique, PhD Thesis of LIRMM, Montpellier, France, (1995). In French.
Steiner, G., Yeomans, J.S.: A Linear Time Algorithm for Maximum Matchings in Convex, Bipartite Graph. In Computers Math. Applic., Vol. 31, No. 12, 91–96, (1996).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beldiceanu, N. (2001). Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family. In: Walsh, T. (eds) Principles and Practice of Constraint Programming — CP 2001. CP 2001. Lecture Notes in Computer Science, vol 2239. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45578-7_15
Download citation
DOI: https://doi.org/10.1007/3-540-45578-7_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42863-3
Online ISBN: 978-3-540-45578-3
eBook Packages: Springer Book Archive