Variety Reasoning for Multiset Constraint Propagation

Abstract

Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this paper, we generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset — the number of distinct elements in it — to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also 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 more search space and achieve better runtime in solving multiset CSPs.Yat Chiu Law, Jimmy Ho Man Lee, May Hiu Chun Woo