Variety Reasoning for Multiset Constraint Propagation

1 Introduction

Many combinatorial design problems can be modeled as constraint satisfaction problems (CSPs) using set variables, which can take collections of distinct elements as their values. The domain of a set variable is typically represented by its set upper and lower bounds [Gervet, 1997] and propagated by enforcing set bounds consistency [Gervet, 1997] together with cardinality reasoning [Azevedo and Barahona, 2000]. By considering also the cardinality of a set variable during propagation, more prunings can be produced than set bounds propagation alone and further reduce the search space.

∗We thank the anonymous referees for their constructive comments. The work described in this paper was substantially supported by grants (CUHK413207 and CUHK413808) from the Research Grants Council of Hong Kong SAR.

Multiset variables are a generalization of set variables by allowing the elements to have repetitions. Consider the template design problem (prob002 in CSPLib) which is to assign some designs to printing templates subject to some constraints. Each template has a fixed number of slots for the designs. One possible modeling is to use an integer variable for each slot in a template. However, this model introduces unnecessary symmetries as the slots are indistinguishable. Since a design can appear multiple times in one template, a more "natural" model is to use a multiset variable for each template to avoid the symmetries. The domain of each variable is the set of all possible multisets of designs that can be assigned to the template. Other than this problem, Frisch et al. listed a collection of ESSENCE specifications 1 containing many problems that can be modeled using multiset variables.

The cardinality of a set reveals the total number of elements in it. Incorporating a cardinality variable to a set variable [Azevedo and Barahona, 2000] enjoys success in enhancing propagation for set constraints. On the other hand, the number of distinct elements, which we call variety, is a property specific to multisets. In this paper, we propose a multiset variable representation which is an improvement over the occurrence representation [Kiziltan and Walsh, 2002; Walsh, 2003]. We incorporate a cardinality variable as well as a variety variable to the representation which do not just allow to express certain problem constraints much more easily (i.e., better modeling expressiveness), but also increase the opportunities to infer more domain prunings for better solving efficiency. We 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 varieties to achieve stronger constraint propagation. We also apply our rules to perform variety reasoning on some common multiset constraints. Experimental results confirm that performing variety reasoning on top of cardinality reasoning can further reduce the search space and give a better runtime in solving multiset CSPs.

2 Background

A constraint satisfaction problem (CSP) is a triple P = (X , D, C), where X = {X1, . . . ,Xn} is a finite set of variables, D = {Dx1 , . . . , Dxn } is a set of finite domains of possible values, and C is a set of constraints. Each constraint involves a subset of the variables in X, limiting the combination of values that the variables in the subset can take. A solution of P is to assign a value to every variable Xi ∈ X from its domain DXi such that all the constraints in C are satisfied.

1 Available at http://www.cs.york.ac.uk/aig/ constraints/AutoModel/Essence/specs120/

A set is an unordered list of elements without repetitions. The cardinality of a set S is the number of elements in S, denoted as |S|. Gervet [1997] proposed to represent the domain of a set variable S with an interval [RS (S), PS(S)] such that DS = {m|RS (S) ⊆ m ⊆ PS(S)}. The required set RS (S) contains all the elements which must exist in the set, while the possible set PS(S) contains any element which may exist in the set. S is said to be bound when its lower bound equals its upper bound (i.e., RS (S) = PS(S)).

Traditional domain reasoning for integer variables is not practical for set variables, as their domains are exponential to the size of possible sets. Gervet [1997] proposed using bounds reasoning to maintain consistency on set variables. A set variable S with set interval domain [RS (S), PS(S)] is set bounds consistent with respect to a constraint C if and only if RS (S) = ⋂ domS(C) and PS(S) = ⋃ domS(C), where domS(C) denotes the domain values of S that satisfy C.

A multiset is a generalization of set by allowing the elements to have repetitions. We denote a multiset S as S = {{· · · }} and its cardinality as |S|. For example, if S = {{1, 1, 2, 2, 3}}, then |S| = 5. In this paper, without loss of generality, we assume that multiset elements are positive integers from 1 to n. We shall use ∅ to denote both the empty set and the empty multiset. Since the number of occurrences of an element in a multiset variable can be more than one, enumerating all possible multisets to represent a multiset variable domain is even more impractical. Thus, Kiziltan and Walsh [2002; 2003] suggested to represent a multiset variable S with n elements by a vector of occurrence (integer) variables 〈occ(1, S), . . . , occ(n, S )〉. Each variable occ(i, S) models the number of occurrences of an element i in S. Its domain is denoted as the interval Docc(i,S) = [occr(i, S), occp(i, S)]. We also define sr as the multiset whose occurrence of each element i is occr(i, S). Similarly, sp is the multiset whose occurrence of each element i is occp(i, S). The multisets sr and sp are in fact the required multiset RS (S) and the possible multiset PS(S) of S respectively (i.e., DS = [RS (S), PS(S)] = [sr, sp]). This occurrence representation is compact but cannot represent all forms of disjunctions. Most set constraints can be generalized to their multiset counterparts. Table 1 gives some common multiset constraints, in which X, Y , and Z are multiset variables and i is an element.

Multiset variables are usually propagated by enforcing multiset bounds consistency, which can be defined using the occurrence representation. A multiset variable S consisting of a vector of occurrence variables occ(i, S) with interval domain [occr(i, S), occp(i, S)] is multiset bounds consistent with respect to a constraint C if and only if occr(i, S) = min(domocc(i,S)(C)) and occp(i, S) = max(domocc(i,S)(C)), where domocc(i,S)(C) denotes the domain values of the number of occurrences of element i in S that satisfy C. This definition is equivalent to the notion BC by Kiziltan and Walsh [2002; 2003].

3 Variety

Amultiset S allows repeated elements. Its cardinality |S| reveals only the total number of elements, but not the number of distinct elements, which we define as variety and denoted as ‖S‖. Note that ‖S‖ can never be greater than |S|. In fact, S degenerates to a set when |S| = ‖S‖ (i.e., the number of occurrences of all elements equals one). In this section, we shall formally define a multiset variable in terms of variety. Then, we describe a naive approach to model variety using metaconstraints, which can hinder propagation. Subsequently, we propose some inference rules which improve over the naive approach. We also demonstrate how variety can help increase propagation for multiset constraints by variety reasoning.

3.1 Multiset Variable with Cardinality and Variety

We define a multiset variable S consisting of three components. The first is a vector of finite domain variables 〈occ(1, S), . . . , occ(n, S )〉 [Kiziltan and Walsh, 2002; Walsh, 2003] modeling the number of occurrences of each element in S. On top of the occurrence representation, the second component is a cardinality variable CS [Azevedo and Barahona, 2000] whose domain is denoted as the interval DCS = [cr, cp], modeling the total number of elements in S (denoted as |S|). The third is a variety variable VS whose domain is denoted as the interval DVS = [vr, vp], modeling the number of distinct elements in S (denoted as ‖S‖).

For example, suppose n = 4 and consider a multiset variable S whose components have the following domains: Docc(1,S) = [0, 1], Docc(2,S) = [0, 2], Docc(3,S) = [0, 3], Docc(4,S) = [0, 1], DCS = [0, 7], and DVS = [0, 4]. Then, we have (1) sr = ∅, as the lower bounds of all the occurrence variables are 0; and (2) sp = {{1, 2, 2, 3, 3, 3, 4}}, as the upper bounds of the occurrence variables of elements 1, 2, 3, and 4 are 1, 2, 3, and 1 respectively. The domain of S is in fact the multiset interval [∅, {{1, 2, 2, 3, 3, 3, 4}}].

Introducing a variety variable to the representation allows us to model the domain of a multiset variable in a more precise way (although still inexact). Consider S in the previous example and suppose we are interested in only the domain values whose varieties are 1. Without the variety variable VS, we can only set DCS to [1, 3]. This domain accepts, for example, the multiset {{1, 2}}, which obviously should not be included. However, with VS, we can simply set DVS = [1, 1] to further remove the multisets which contain more than one kind of elements. This essentially models DS = {{{1}}, {{2}}, {{2, 2}}, {{3}}, {{3, 3}}, {{3, 3, 3}}, {{4}}}, a much more precise representation.

Another advantage is to improve modeling expressiveness by allowing to post variety constraints to limit the number of distinct elements in multiset variables. For example, in the template design problem, we may want to restrict a template T to have at most three distinct designs in its slots. Using our representation, posting a variety constraint ‖T ‖ ≤ 3 simply means to propagate the simple unary constraint VT ≤ 3. Without VT , we need to post a number of meta-constraints to model the requirement, which may hinder propagation. The advantage becomes more obvious when the form of the variety constraints is more complicated, e.g., ‖T1‖ + ‖T2‖ ≤ 4. The next subsection describes the naive approach of using meta-constraints to model variety.

3.2 Naive Approach

Consider a multiset variable S with its three components: occurrence occ(i, S) where i is the possible elements in S, cardinality CS , and variety VS . We can model the cardinality CS and the variety VS using the constraints CS = ∑i occ(i, S) and VS = ∑i (occ(i, S) > 0) for each distinct element i in S respectively. Note that the latter one is a meta-constraint. Its propagation is usually weak in most constraint solvers. In fact, propagating the meta-constraints neglects the direct relationship between VS and CS, and also the more complicated relationship among occ(i, S), CS, and VS, as can be shown in the following example.

Consider two multiset variables S1 and S2 where DS1 = [{{1}}, {{1, 2, 3, 3}}] (i.e., Docc(1,S1) = [1, 1], Docc(2,S1) = [0, 1], Docc(3,S1) = [0, 2]), DCS1 = [3, 3], DVS1 = [1, 3], and DS2 = [{{1}}, {{1, 4, 5, 5}}] (i.e., Docc(1,S2) = [1, 1], Docc(4,S2) = [0, 1], Docc(5,S2) = [0, 2]), DCS2 = [3, 3], DVS2 = [1, 3]. Suppose we now post a constraint in which the variety of the union-plus of S1 and S2 is not greater than 3 (i.e., ‖S1 ⊎ S2‖ ≤ 3). Reasoning on this constraint reveals that S1 and S2 cannot contain elements 2 and 4 respectively, because the cardinalities of both S1 and S2 must be 3 and their union-plus can contain at most three different elements. S1 and S2 should then be bound to {{1, 3, 3}} and {{1, 5, 5}} respectively. However, using the meta-constraint ∑5i=1 (occ(i, S1) + occ(i, S2) > 0) ≤ 3, the domains of S1 and S2 remain unchanged.

By exploiting the relationships between the three components of a multiset variable, we propose a number of inference rules to strengthen propagation. In the next subsection, we shall systematically enumerate the possible relationships.

3.3 Inferences within OneMultiset Variable

Upon creation of a multiset variable S, the vector of occurrence variables 〈occ(1, S), . . . occ(n, S )〉, the cardinality variable CS, and the variety variable VS will also be created. A number of inference rules are subsequently maintained. Inferences occur between any two kinds of variables (i.e., between occ(i, S) and CS, between occ(i, S) and VS, or between CS and VS), or among all three of them. Inference rules will be formally described as rewriting rules as in the following schematic figure:

(trigger condition) conditions(which can be nil)

changes in constraint store

(1) Inferences between occ(i, S) and CS

The cardinality CS must always remain inside the limits given by the multiset bounds sr and sp [Azevedo and Barahona, 2000]. (Recall that sr and sp can be computed using the occurrence variables.)

The cardinality CS is the sum of the number of occurrences of all elements in a multiset variable. Thus, the number of occurrences of each element is updated when there are changes in the lower bound cr and the upper bound cp of the cardinality variable. Here, we only concern with the elements that have not yet been included in the lower bound (i.e., sp \ sr, which is defined as occ(i, sp \ sr) = max{0, occ(i, sp) - occ(i, sr)} for all elements i).

(CS changed bounds)

For example, consider a multiset variable S where DS = [{{1, 1}}, {{1, 1, 1, 2, 2, 3}}] (i.e., Docc(1,S) = [2, 3], Docc(2,S) = [0, 2], Docc(3,S) = [0, 1]), DVS = [1, 3], and cp is updated from 6 to 3 (i.e., DCS = [2, 3]). Since S can now have at most three elements of at most two different kinds, and there are already two 1s in the required set, only one more element (1, 2, or 3) may exist in S. Based on the inference rule, K = sp \ sr = {{1, 1, 1, 2, 2, 3}} \ {{1, 1}} = {{1, 2, 2, 3}} and occ(i, K) ≤ β - |sr| = 3 - 2 = 1 for i = 1, 2, 3. Thus, one of the 2s is removed, resulting Docc(2,S) = [0, 1] and DS = [{{1, 1}}, {{1, 1, 1, 2, 3}}].

(2) Inferences between occ(i, S) and VS

The variety VS must always remain inside the limits given by the multiset bounds. This is generalized from the inferences between occ(i, S) and CS [Azevedo and Barahona, 2000].

The occurrence of each element occ(i, S) will be updated only when VS is bound and equals either ‖sr‖ or ‖sp‖. When the variety VS is fixed and equals ‖sr‖, any elements i that are not in sr (i.e, occr(i, S) = 0) have to be removed (i.e., occ(i, S) = 0 for those i). On the other hand, if VS = ‖sp‖, then each element in sp (i.e, occp(i, S) > 0) must occur at least once in S (i.e., occ(i, S) > 0 for those i).

For example, consider a multiset variable S where DS = [{{1, 1}}, {{1, 1, 2, 2, 3}}] (i.e., Docc(1,S) = [2, 2], Docc(2,S) = [0, 2], Docc(3,S) = [0, 1]), DCS = [2, 5], and VS is bound to 1. Since VS = ‖sr‖ (i.e., 1 = ‖{{1, 1}}‖) and the elements 2 and 3 are not yet in sr, they will not exist in S, resulting occ(2, S) = occ(3, S) = 0.

Consider the same multiset variable S but VS is now bound to 3. Since VS = ‖sp‖ (i.e., 3 = ‖{{1, 1, 2, 2, 3}}‖) and the elements 2 and 3 are not yet in sr, at least one occurrence of 2 and 3 has to be added to their lower bound, resulting occr(2, S) = occr(3, S) = 1. Here, occr(1, S) remains unchanged because the element 1 is already in its lower bound.

(3) Inferences between CS and VS

The variety must always be smaller than or equal to the cardinality at both limits because cardinality counts same elements but variety does not.

(4) Inferences among occ(i, S), CS, and VS

When any two of occurrences occ(i, S), cardinality CS, and variety VS change their bounds, the remaining one has to be updated as well. This kind of inferences lead to stronger constraint propagation than those between the pairwise ones (i.e., between occ(i, S) and CS, between occ(i, S) and VS, and between CS and VS).

When the occurrences occ(i, S) and the variety VS change their bounds, the cardinality CS will be adjusted accordingly to fulfill the requirements on VS based on the elements existing in sp \ sr.

(S or VS changed bounds)

For example, consider a multiset variable S which updates its bounds to DS = [{{1, 1}}, {{1, 1, 1, 2, 2, 3}}] (i.e., Docc(1,S) = [2, 3], Docc(2,S) = [0, 2], Docc(3,S) = [0, 1]), DCS = [2, 6], andDVS = [2, 3]. Since S must contain at least two different kinds of elements, besides element 1, either element 2 or 3 has to be included in S. This lead to an increase in cr although the exact addition has not yet taken place. Based on the inference rule, CS ≥ |sr|+(α-‖sr‖) = 2+2-1 = 3. Thus, DCS is updated to [3, 6].

To find a, the subset sp \ sr, which fulfills the condition ‖b ⊎ sr‖ = β, is first extracted. The possible elements are then ordered. Thus, the complexity is bounded by the sorting procedure O(n log n), where n is the number of distinct elements in S.

Similarly, when the occurrences occ(i, S) and the cardinality CS change their bounds, the variety VS will be adjusted accordingly to fulfill the requirements on CS based on the elements existing in sp \ sr.

For example, consider a multiset variable S which updates its bounds to DS = [{{1, 1}}, {{1, 1, 1, 2, 2, 3}}] (i.e., occ(1, S) = [2, 3], occ(2, S) = [0, 2], occ(3, S) = [0, 1]), DVS = [1, 3], and cr is updated from 2 to 4 (i.e., DCS = [4, 6]). Here, S must contain at least four elements. With the current vr, S can only have at most three 1s and one more element is needed to reach cr. Other elements, which lead to a minimal change in vr, are selected from their upper bounds. Based on the inference rule, b refers to a subset of (sp \ sr) where D(sp\sr) = [∅, {{1, 2, 2, 3}}] and the cardinality of b⊎sr equals cr (i.e., 4). Thus, vr equals the minimum variety of the union of sr and a possible b (i.e., ‖{{1, 1}} ∪ {{1, 2}}‖ = 2). VS is updated to [2, 3].

a and c can be obtained using the same way as finding a in the previous inference rule, but with different conditions. Thus, the complexity for this inference rule as a whole is also bounded by the sorting procedure O(n log n), where n is the number of distinct elements in S.

When the cardinality CS is fixed and equals either |sr| or |sp|, S can be set to the corresponding bound (i.e., all occurrences occ(i, S) can be fixed) and VS can also be bound accordingly.

When both the cardinality CS and the variety VS are bound to the same value α, S degenerates to a set. Thus, the occurrence of each element occ(i, S) will be at most one.

(5) Failure

A failure can be detected when any one of the conditions is true: (1) the lower bound sr is not included in the upper bound sp; or (2) the domain of the cardinality variable DCS becomes empty; or (3) the domain of the variety variable DVS becomes empty.

The inference rules described in this subsection are incomplete in the sense that they only enforce bounds consistency on the component variables. They do not enforce the strongest possible consistency, as it is intractable in general.

Theorem 1. Enforcing GAC on a multiset variable consisting of occurrence, cardinality, and variety variables is NP-hard.

Proof. Enforcing GAC on any general constraints on integer variables is NP-hard [Bessiere et al., 2007]. An integer variable is a special case of a multiset variable, which degenerates to an integer variable when both cardinality and variety equal 1. Hence the result.

In fact, our primary aim is not for completeness, but for inference rules that are efficiently implementable. Nonetheless, the inference rules as a whole maintain more than multiset bounds consistency.

Theorem 2. The inference rules (1) between occ(i, S) and CS, (2) between occ(i, S) and VS, (3) between CS and VS, (4) among occ(i, S), CS, and VS, and (5) for failure collectively enforce a consistency level strictly stronger than multiset bounds consistency.

Proof. Due to space limitations, we skip the proof that our inference rules are at least as strong as multiset bounds consistency. For strictness, the two examples under "(4) Inferences among occ(i, S), CS, and VS" show that given a domain which is already multiset bounds consistent, the inference rules can further tighten the bounds of CS or VS. Hence the result.

3.4 Multiset Constraints

The previous subsection describes the inferences within one multiset variable. In this subsection, we focus on propagation that occurs across different multiset variables. We give some constraint propagation rules that enforce bounds consistency on some common multiset constraints. Performing inferences on the cardinality and variety variables are known as cardinality reasoning and variety reasoning respectively. For each multiset constraint, we use an example to show how they are useful in increasing constraint propagation. In the rules, the changes in the constraint store involving the cardinality variables are adopted from Azevedo and Barahona [2000], but those involving the variety variables are more generalized.

Equality Constraint (X = Y )

If X and Y are told to be equal, then their cardinalities and varieties are also equal respectively.

{X = Y } ↦→ {occ(i, X) = occ(i, Y ), CX = CY , VX = VY }

For example, consider the equality constraint X = Y , where n = 3, Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 2], DCX = [4, 4], DVX = [2, 2], Docc(1,Y ) = [0, 2], Docc(2,Y ) = [0, 2], Docc(3,Y ) = [0, 2], DCY = [4, 4], and DVY = [3, 3]. Without the variety variables VX and VY (and thus without variety reasoning), there are no prunings available. However, with variety reasoning, the problem fails immediately because when X = Y (i.e., occ(i,X ) = occ(i, Y ) for all elements i), VX = VY is obviously violated.

Subset Constraint (X ⊆ Y )

If Y contains X, then CY is greater than or equal to CX, and VY is also greater than or equal to VX.

{X ⊆ Y } ↦→ {occ(i, X) ≤ occ(i, Y ), CX ≤ CY , VX ≤ VY }

Consider the subset constraint X ⊆ Y , where DX = [∅, {{1, 1, 2, 2, 3, 3, 3}}] with cardinality 5 and variety 3 (i.e., Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 3]), DCX = [5, 5], DVX = [3, 3], and DY = [∅, {{1, 1, 2, 2, 3, 3, 3}}] with cardinality 5 and variety 2 (i.e., Docc(1,Y ) = [0, 2], Docc(2,Y ) = [0, 2], Docc(3,Y ) = [0, 3]), DCY = [5, 5], DVY = [2, 2]. With variety reasoning, the problem fails immediately because VX can never be smaller than or equal to VY (i.e., 3 ̸≤ 2). Again, without variety reasoning, there are no available prunings.

Union Constraint (X ∪ Y = Z)

Union takes the maximum number of occurrences of each element. When Z is the union of X and Y , occ(i, Z ) = max(occ(i, X ), occ(i, Y )) for all elements i. CZ (resp. VZ) is smaller than or equal to CX + CY (resp. VX + VY ). On the other hand, the lower bound of CZ (resp. VZ) can be obtained from the maximum of the following two cases: (1) Suppose SZ contains SX (i.e., SX ⊆ SZ), SZ will have at least CX elements (resp. VX distinct elements). We can safely add the elements which appear in SY but not in SX (i.e., yr \ xp) to SZ because SZ is the multiset union and it takes all elements in both SX and SY . Thus, CZ ≥ CX + |yr \ xp| (resp. VZ ≥ VX + ‖yr \ xp‖). (2) Similarly, we can add the elements in (xr \ yp) to SZ if SZ contains SY . Thus, CZ ≥ CY + |xr \ yp| (resp. VZ ≥ VY + ‖xr \ yp‖).

{X ∪ Y = Z} ↦→ {occ(i, Z) =max(occ(i,X), occ(i, Y )), occ(i, X) ≤ occ(i, Z), occ(i, Y ) ≤ occ(i, Z), CZ ≤ CX + CY , VZ ≤ VX + VY , CZ ≥ max(CX + |yr \ xp|, CY + |xr \ yp|), VZ ≥ max(VX + ‖yr \ xp‖, VY + ‖xr \ yp‖)}

Consider the union constraint X ∪ Y = Z, where DX = [∅, {{1, 1, 2, 2, 3, 3}}] (i.e., Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 2]), DCX = [1, 2], DVX = [1, 1], DY = [∅, {{1, 1, 2, 2, 3, 3}}], (i.e., Docc(1,Y ) = [0, 2], Docc(2,Y ) = [0, 2], Docc(3,Y ) = [0, 2]), DCY = [1, 2], DVY = [1, 1], and DZ = [{{1, 2, 3}}, {{1, 1, 2, 2, 3, 3}}], (i.e., Docc(1,Z) = [1, 2], Docc(2,Z) = [1, 2], Docc(3,Z) = [1, 2]), DCZ = [3, 6], DVZ = [3, 3]. With variety reasoning, the problem fails immediately because VZ can never be smaller than or equal to the sum of VX and VY . Without reasoning on the three variety variables, the problem will not fail even when 3 ̸≤ 1 + 1.

Union-Plus Constraint (X ⊎ Y = Z)

When Z is the union-plus of X and Y , CZ equals CX + CY because union-plus sums up all the elements in both X and Y . For all elements i, occ(i, Z ) = occ(i, X ) + occ(i, Y ). However, VZ is smaller than or equal to VX + VY because X and Y can contain the same kind of elements (i.e., ‖X‖ + ‖Y ‖ ̸= ‖X ⊎ Y ‖). For the lower bound of VZ, it can be obtained in the same way as in the union constraint.

{X ⊎ Y = Z} ↦→ {occ(i, Z) = occ(i,X) + occ(i, Y ), occ(i, X) ≤ occ(i, Z), occ(i, Y ) ≤ occ(i, Z), CZ = CX + CY , VZ ≤ VX + VY , VZ ≥ max(VX + ‖yr \ xp‖, VY + ‖xr \ yp‖)}

Consider a union-plus constraint X ⊎ Y = Z, where DX = [∅, {{1, 1, 2, 2, 3, 3}}] (i.e., Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 2]), DCX = [1, 2], DVX = [1, 1], DY = [∅, {{1, 1, 2, 2, 3, 3}}] (i.e., Docc(1,Y ) = [0, 2], Docc(2,Y ) = [0, 2], Docc(3,Y ) = [0, 2]), DCY = [1, 2], DVY = [1, 1], and DZ = [{{1, 2, 3}}, {{1, 1, 2, 2, 3, 3}}] (i.e., Docc(1,Z) = [1, 2], Docc(2,Z) = [1, 2], Docc(3,Z) = [1, 2]), DCZ = [3, 6], DVZ = [3, 3]. Variety reasoning fails the problem immediately because VZ can never be smaller than or equal to the sum of VX and VY . Without reasoning on the three variety variables, the problem will not fail even when 3 ̸≤ 1 + 1.

Intersection Constraint (X ∩ Y = Z)

If Z is the intersection of X and Y , then CZ is smaller than or equal to both CX and CY , and VZ is also smaller than or equal to both VX and VY . This is because intersection takes the minimum number of occurrence of each element between X and Y (i.e., occ(i, Z ) = min(occ(i, X ), occ(i, Y )) for all elements i). The upper bound of CZ (resp. VZ) can be obtained from the minimum of the following two cases. (1) For the elements existing only in xr but not in yp (i.e., xr \ yp), they must not be part of the intersection. We can safely subtract these elements from CX (resp. subtract these kinds of elements from VX), resulting CZ ≥ CX - |xr \ yp| (resp. VZ ≥ VX - ‖xr \ yp‖). (2) Similarly, we can subtract the elements that exist in yr but not in xp (i.e., yr \ xp) from CY (resp. subtract these kinds of elements from VY ), resulting CZ ≥ CY - |yr \ xp| (resp. VZ ≥ VY -‖yr \ xp‖).

{X ∩ Y = Z} ↦→ {occ(i, Z) =min(occ(i,X), occ(i, Y )), occ(i, Z) ≤ occ(i, X), occ(i, Z) ≤ occ(i, Y ), CZ ≤ min(CX, CY ), VZ ≤ min(VX, VY ), CZ ≥ min(CX - |xr \ yp|, CY - |yr \ xp|), VZ ≥ min(VX - ‖xr \ yp‖, VY - ‖yr \ xp‖)}

Consider an intersection constraint X ∩ Y = Z, where DX = [∅, {{1, 1, 2, 2, 3, 3, 3}}] (i.e., Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 3]), DCX = [1, 3], DVZ = [1, 1], DY = [∅, {{1, 1, 2, 2, 3, 3, 3}}] (i.e., Docc(1,X) = [0, 2], Docc(2,X) = [0, 2], Docc(3,X) = [0, 3]), DCY = [1, 3], DVY = [1, 1], and DZ = [∅, {{1, 2, 3, 3, 3}}] (i.e., Docc(1,X) = [0, 1], Docc(2,X) = [0, 1], Docc(3,X) = [0, 3]), DCZ = [2, 4], DVZ = [2, 2]. With variety reasoning, the problem fails immediately because VZ can never be smaller than or equal to both VX and VY . The problem will not fail without variety reasoning even when 2 ̸≤ 1.

4 Experimental Results

To verify the feasibility and efficiency of our proposal, we implement our multiset variable representation, the inference rules, and the multiset constraints in ILOG Solver 6.0 [ILOG, 2003]. We use the extended Steiner system and the template design problem as the benchmark problems. While the standard Steiner system is only set-based, the extended version is an important and practical multiset problem in the area of information retrieval [Johnson and Mendelsohn, 1972; Bennett and Mendelsohn, 1980; Park and Blake, 2008]. Solving the extended Steiner system can provide solutions to the problem of a multiset batch code.

The extended Steiner system ES (t, k, v) is a collection of b blocks. Each block is a k-element multiset drawn from a v-element set whose elements can be drawn multiple times. For every two blocks in the collection, the cardinality of their intersection must be smaller than t. For example, one possible solution for ES (2, 3, 3) in 3 blocks is {{{1, 1, 2}}, {{2, 2, 3}}, {{3, 3, 1}}}. The intersection of {{1, 1, 2}} and {{2, 2, 3}} is {{2}}; the intersection of {{1, 1, 2}} and {{3, 3, 1}} is {{1}}; the intersection of {{2, 2, 3}} and {{3, 3, 1}} is {{3}}. All of them have size smaller than t = 2. In our experiments, we adapt the extended Steiner system to an optimization problem which maximizes the sum of the varieties of the multisets in a solution. To further increase problem difficulty, we also constrain each multiset to have at least certain varieties.

The experiments are run on a Sun Blade 2500 (2 × 1.6GHz US-IIIi) workstation with 2GB memory. We report the number of fails (i.e., the number of backtracks occurred in solving a model) and CPU time in seconds to find and prove the optimal solution for each instance. Comparisons are made among set bounds consistency (SB), set bounds consistency with cardinality reasoning (SB+CR), and set bounds consistency with cardinality and variety reasoning (SB+CR+VR) proposed in this paper. We use the naive approach mentioned in Section 3.2 to model the cardinality variables in SB, and the variety variables in both SB and SB+CR. The meta-constraints are enforced by the built-in propagation algorithms in ILOG Solver instead of the inference rules. In the tables, the best number of fails and CPU time among the results for each instance are highlighted in bold. A cell labeled with "-" denotes a timeout after one hour.

Tables 2 and 3 show the experimental results of the maximization and the variety of each multiset is at least 2 and 3 respectively. Among the three propagation approaches, SB+CR+VR always achieves the fewest number of fails. There are more than 90% reduction in number of fails when compared to SB alone, and more than 50% reduction when compared to SB+CR. This confirms that variety (and cardinality) reasoning is highly effective in reducing search space. The extra prunings are so significant that they compensate the overhead of extra computational effort spent for variety (and cardinality) reasoning. For runtime, SB+CR+VR is also always the fastest, although the proportion of reduction is less than that for the number of fails. The reduction of SB+CR+VR over SB+CR in Table 2 is moderate, but that in Table 3 is significant. There are even instances in which both SB and SB+CR cannot finish execution within the time limit, but SB+CR+VR can. This also shows that the usefulness of variety reasoning sometimes depends on the tightness of the variety constraints in a problem.

For the template design problem, each multiset variable represents a template and its domain values are the possible combinations of designs which allow repetitions. Like the extended Steiner system, we further impose a restriction to constrain the varieties of each multiset. Due to space limitations, we do not show the tables, but from the experimental results, SB+CR+VR always achieves the fewest number of fails. There are at least 20% reduction in the number of fails when compared to SB and SB+CR. When the problem instance has no solutions, enforcing SB+CR+VR can even reduce the search space by up to 70%. The savings in runtime, however, is not as significant as those in the extended Steiner system. The performance difference of SB+CR+VR between the satisfiable and unsatisfiable instances is an interesting phenomenon which we are still investigating.

Note that our current implementation of the multiset variable representation and the rules is only prototypical. There are still rooms for improvement. For example, it is known that adjusting the triggering order of the rules (depending on the computational cost of the rules) can affect the performance [Azevedo and Barahona, 2000]. We expect that our implementation can be optimized in the future.

5 RelatedWork

Conjunto [Gervet, 1997] is the first constraint solver developed in which a set variable is represented by set intervals. Other set constraint solvers include Oz [M¨uller and M¨uller, 1997], Mozart [M¨uller, 2001], and ROBDD [Lagoon and Stuckey, 2004; Hawkins et al., 2005]. Azevedo and Barahona [2000] further proposed cardinality reasoning on set constraints and developed another set constraint solver, Cardinal, to handle the set cardinality more actively and improve the performance in solving CSPs with set variables.

Kiziltan and Walsh [2002; 2003] suggested three multiset representations: bounds, occurrence, and fixed cardinality representations. They proved that occurrence representation is more expressive than bounds representation when maintaining domain consistency, and is as expressive as when maintaining bounds consistency. Fixed cardinality representation is incomparable to the other two. All three of them are compact but cannot represent all forms of disjunctions.

6 Conclusion

We have introduced cardinality and variety variables to multiset variables based on the occurrence representation. While the introduction of cardinality variable is a straightforward generalization to the set variable counterpart, the idea of variety variable is a new concept. We have exploited the variety property to introduce new inference rules to increase pruning opportunities, and improved the propagation of some common multiset constraints through variety reasoning.

There can be plenty of scope for future research for multiset CSPs. An example is to perform variety reasoning on other multiset global constraints like the disjoint and partition constraints. Other multiset-specific properties can also be incorporated into multiset variable representations to even further enhance constraint propagation.