Multiset variable representations and constraint propagation (Q481702)

The authors study representations of multiset variables from a formal perspective, the consistency and propagation of constraints involving multiset variables. They identify a number of different representations for multiset variables and compare them in terms of effectiveness and efficiency. They propose inference rules to enforce bounds consistency for the representations as well as to exploit the variety (i.e., the number of distinct elements) of a multiset in order to improve the modeling expressiveness and to further enhance constraint propagation. Also, they derive a number of inference rules involving the varieties of multiset variables and show how the traditional components of multiset variables (such as cardinalities) interact with the variables to achieve stronger constraint propagation. Finally, they demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce the search space and achieve better runtime in solving multiset CSPs.