Abstract
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. That is, variables whose values are multisets. These help us model problems more naturally and can, for example, prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables and compare them. We then propose a definition of local consistency for constraints involving multiset, set and integer variables. This definition is a generalization of the notion of bounds consistency for integer variables. We show how this local consistency property can be enforced by means of some simple inference rules which tighten bounds on the variables. We also study a number of global constraints on set and multiset variables. Surprisingly, unlike finite domain variables, the decomposition of global constraints over set or multiset variables often does not hinder constraint propagation.
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
Gervet, C.: Conjunto: constraint logic programming with finite set domains. In: Bruynooghe, M. (ed.) Proc. of the 1994 Int. Symp. on Logic Programming, pp. 339–358. MIT Press, Cambridge (1994)
Müller, T., Müller, M.: Finite set constraints in Oz. In: Bry, F., Freitag, B., Seipel, D. (eds.) 13th Logic Programming Workshop, TU München, pp. 104–115 (1997)
Proll, L., Smith, B.: Integer linear programming and constraint programming approaches to a template design problem. INFORMS Journal on Computing 10, 265–275 (1998)
Gervet, C.: Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. Constraints 1, 191–244 (1997)
Régin, J.: A filtering algorithm for constraints of difference in CSPs. In: Proc. of the 12th National Conference on AI, American Association for AI, pp. 362–367 (1994)
Beldiceanu, N.: Global constraints as graph properties on a structured network of elementary constraints of the same type. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 52–66. Springer, Heidelberg (2000)
Gent, I., Stergiou, K., Walsh, T.: Decomposable constraints. Artificial Intelligence 123, 133–156 (2000)
Dovier, A., Piazza, C., Pontelli, E., Rossi, G.: Set and constraint logic programming. ACM Trans. on Programming Languages and Systems 22, 861–931 (2000)
Legeard, B., Legros, E.: Short overview of the CLPS system. In: Małuszyński, J., Wirsing, M. (eds.) PLILP 1991. LNCS, vol. 528, pp. 431–433. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Walsh, T. (2003). Consistency and Propagation with Multiset Constraints: A Formal Viewpoint. 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_49
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive