Constraint Programming with Multisets
Zeynep Kiziltan, Walsh Toby · 2002
Abstract. We propose extending constraint solvers with multiset variables. That is, variables whose values are multisets. Such an extension can help prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables, and suggest primitive and global constraints on multiset variables. Surprisingly, unlike finite domain variables, decomposition of global constraints on multiset variables often does not hinder constraint propagation. We also study in detail the multiset ordering constraint. This constraint is useful for breaking symmetry between multiset variables. We show how it can be enforced using a simple lexicographical ordering constraint. 1