Multiset Ordering Constraints

1 Introduction

Global (or non-binary) constraints are one of the factors cen­ tral to the success of constraint programming [Regin, 1994; 1996; Beldiceanu, 2000]. Global constraints specify patterns that occur in many problems, and call efficient and effective constraint propagation algorithms. In this paper, we identify a new and important global constraint. This constraint en­ sures that the values taken by two vectors of variables, when viewed as multisets, are ordered. Such a constraint is use­ ful in a number of domains. For example, in the progressive party problem (prob013 in csplib.org), we wish to assign a host for each guest and period. We can model this with avec­ tor of variables for each period. Each variable is assigned the host for a particular guest. This model has unnecessary sym­ metry as the periods can be freely permuted. We can break this symmetry by considering the multiset of values associ­ ated with each vector and ordering these multisets.The aim of this paper is to study such multiset ordering constraints and to develop efficient and effective techniques for enforcing them.

2 Formal Background

A constraint satisfaction problem (CSP) consists of a set of variables, each with a finite domain of values, and a set of constraints that specify allowed values for subsets of vari­ ables. A solution is an assignment of values to the variables satisfying the constraints. To find such solutions, we explore partial assignments enforcing a local consistency like gener­ alized arc-consistency (GAC). A constraint is GAC iff, when a variable in the constraint is assigned a value v, compatible values exist for all the other variables in the constraint. Such compatible values are referred as the support for v. GAC reduces to node-consistency (NC) for unary constraints. Fi­ nally, a constraint is bounds consistent (BC) iff, when a vari­ able in the constraint is assigned its maximum or minimum value, there exist compatible values for all the other variables in the constraint. If a constraint cis NC, BC, or GAC then we write NC(c), BC(c), or GAC(c) respectively.

*Support received by EPSRC under GRIR30792 and by the Sci­ ence Foundation Ireland. We thank Chris Beck and Chris Jefferson.

A multiset is an unordered list in which repetition is al­ lowed. A multiset M is ordered smaller than another N, written M -<m N iff either M is empty and N is not, or the largest value in M is smaller than the largest value inN, or the largest values are the same and, if we eliminate one occurrence of the largest value from both M and N, there­ sulting two multisets are ordered. Note that M :::Sm N iff M = N or M -<m N. We will often view the values taken by a vector of variables as a multiset. Given two vectors of variables, x and y, we write a multiset ordering constraint as x ::;m y. This constraint is satisfied iff the values for the variables in the vectors, when treated as multisets, satisfy the multiset ordering. Similarly, we write a strict multiset order­ ing constraint as x <m fj. Throughout the paper, we assume that vectors of variables have finite integer domains, and the variables are disjoint and not repeated.

Vectors of variables are indexed from 0. The minimum element in the domain of Xi is min( xi), and the maximum is max(xi)· The functionfioor(x) assigns all variables in x to their minimum values, whilst ceil(x) assigns all to their maximums. The vector Xv=d is identical to x except v now has the domain { d}. An occurrence vector occ( x) associ­ ated with xis indexed in decreasing order from the maximum max(x) to the minimum min(x) value from the domains in x. The ith element of occ(x) is the number of occurrences of max(x) - i in x. When comparing two occurrence vectors, we assume they start and end with the occurrence of the same value, adding leading/ trailing zeroes as necessary. Finally, x ::;lex y iff xis lexicographically less than or equal to y.

3 Motivating applications

3.1 Matrix symmetry

Many constraints programs contain matrices of decision vari­ ables (so called "matrix models"), and the rows and/or columns of these matrices are symmetric and can be permuted [Flener eta/., 2002]. Such symmetries are very difficult to deal with as there are a super-exponential number of permu­ tations of the rows or columns to consider. There are several ways to break symmetry in a CSP, such as SBDS [Gent and Smith, 2000] or SBDD [Fable eta/., 2001]. One of the most effective, and the one which we will concentrate on as a major application for a multiset ordering constraint, is adding extra symmetry-breaking constraints to an initial model. Existing techniques for dealing with such symmetries typically elimi­ nate only some of the symmetry. Additional techniques, like those proposed here, are therefore of considerable value.

The progressive party problem mentioned earlier has a 2d matrix of decision variables with matrix symmetry. The rows of the matrix are the guests, the columns are the periods. Each variable gives the host assigned to a given guest in a given pe­ riod. As periods are indistinguishable, the columns of the ma­ trix are symmetric. One way to break such column symmetry is to lex order the columns [Frisch eta/., 2002]. Similarly, as guests can be indistinguishable, (some of) the rows may be symmetric and can be lex ordered. Alternatively, we can treat each row and/or column as a multiset and break such symmetry by multiset ordering the rows and/or columns.

Unlike lex ordering, multiset ordering the rows of a matrix may not eliminate all row symmetry. For example, consider the symmetric matrices:

Both satisfy the constraint that the first row is multiset less than the second. It is therefore a little surprising to dis­ cover that multiset ordering (which does not break all row symmetry) is not dominated by lex ordering (which does) but is incomparable. For example, (0, 2) ~lex (1, 1) but (1, 1) ~m (0, 2).

When we have both row and column symmetry, we can multiset order both rows and columns. Like lex ordering both rows and columns, this may not eliminate all row and column symmetry. Consider the symmetric matrices:

Both have multiset ordered rows and columns. Unsurpris­ ingly, multiset ordering rows and columns is incomparable to lex ordering rows and columns. Consider the symmetric matrices:

The first has lex ordered rows and columns, but the columns are not multiset ordered. The second has rows and columns that are multiset ordered but the columns are not lex ordered.

An alternative way to deal with row and column symmetry is to multiset order in one dimension and apply the symme­ try breaking method of our choice in the other dimension. This is one of the best features of using multiset ordering to break symmetry. It {s compatible with any other method in the other dimension. For instance, we can multiset order the rows and lex order the columns. Preliminary results in [Kizil­ tan and Smith, 2002] suggest that such a combined method is very promising. This combined method does not eliminate all symmetry (but it is unlikely that any polynomial set of constraints does). Consider the symmetric matrices:

Both have rows that are multiset ordere , and rows and columns that are lex ordered. Multiset ordering the rows and lex ordering the columns is again incomparable to lex order­ ing rows and columns. Consider the symmetric matrices:

The first matrix has rows that are multiset ordered and columns that are lex ordered. However, its rows are not lex ordered. The second matrix has rows and columns that are lex ordered but does not have rows that are multiset ordered. Whilst the two orderings are theoretically incomparable, our experimental results (see later) show that multiset ordering the rows and lex ordering the columns is often the most ef­ fective symmetry breaking constraint currently known.

3.2 Fuzzy constraints

Another application for multiset ordering is to fuzzy CSPs. A fuzzy constraint associates a degree of satisfaction to an as­ signment tuple for the variables it constrains. To combine de­ grees of satisfaction, we can use a combination operator like the minimum function. Unfortunately, the minimum function may cause a drowning effect when one poorly satisfied con­ straint 'drowns' many highly satisfied constraints. One solu­ tion is to collect a vector of degrees of satisfaction, sort these values in ascending order and compare them lexicographi­ cally. This leximin combination operator identifies the as­ signment that violates the fewest constraints [Fargier, 1994]. This induces an ordering identical to the multiset ordering ex­ cept that the lower elements of the satisfaction scale are the more significant. It is simple to modify a multiset ordering constraint to consider the values in a reverse order. To solve such leximin fuzzy CSPs, we can then use branch and bound, adding an ordering constraint when we find a solution to en­ sure that future solutions are greater in the leximin ordering.

4 GAC algorithm for multiset ordering

The last section motivated why we want multiset ordering constraints. We need, however, to be able to propagate such constraints efficiently. We therefore developed an efficient GAC algorithm for such constraints.

4.1 Background

The algorithm exploits two theoretical results. The first re­ duces the problem to testing support for upper bounds of x and lower bounds of y on suitable ground vectors. The sec­ ond reduces these tests to lex ordering suitable occurrence vectors. Identical results hold for the strict multiset ordering constraint but for reasons of space we omit them here.

Lemma 1 Given two disjoint and non-repeating vectors of variables, x and if, with non-empty domains, GAC(x ~m Y) iff 'r:/xi E x, 'r:/yi E y:

Proof: ( =>) As the constraint is GAC, all values have sup­ port. In particular, Xi = max(xi) has support. The best support comes if all the other variables in x take their mini­ mums, and all the variables in ytake their maximums. Hence, fioor(xx,=max(x;)) ~m ceil(iJ) . Similarly, for Yi·

( ¢::) The first constraint ensures that max (Xi) is supported. The values which support max(xi) also support all smaller values. Hence, all the values in the domain of Xi are sup­ ported. By an analogous argument, all the values in the do­ main ofyi are supported. Hence the constraint is GAC. QED.

The next lemma reduces these tests for support to lex or­ dering suitable occurrence vectors.

Lemma 2 Given two multisets of values, M and N , M ~m N iffocc(M) ~lex occ(N) .

Proof: See [Kiziltan and Walsh, 2002] .

4.2 A worked example

Based on these lemmas, we have designed an efficient algo­ rithm for enforcing GAC on a multiset ordering constraint. The algorithm goes through the Xi and Yj checking for sup­ port in the appropriate occurrence vectors. Incremental com­ putation of the lex ordering test avoids repetition of work. Consider the multiset ordering constraint x ~m y where:

We construct occurrence vectors forjloor(x) and ceil(i!), in­ dexed from 5 to 0:

occ(jloor(x)) occ(ceil(if)) (1, 1, 1, 1, 2, 0) (1, 2, 1, 0, 1, 1)

Recall that index i in occ( ceil(iJ)) denotes the number of occurrences of the value i in ceil(iJ). For example, index 4 is 2 as the value 4 occurs twice.

We first check if occ(floor( x)) >lex occ( ceil(i!)). If so, we can fail immediately because no value for any variable can have support. Here, occ(floor(x)) ~lex occ(ceil(Y)). In fact, we record (in a pointer, a) that the two occurrence vectors are lex ordered by index 4 of occ(floor(x)), which is strictly smaller than index 4 of occ(ceil(iJ)). This means that we will fail to find support in the Yj if any of the Xi is assigned a new value greater than 4. We now go through the Xi checking for support for their maximum values, and then the Yi checking for support for their minimum values.

Consider x0 . As it has a singleton domain, and occ(floor(x)) ~lex occ(ceil(iJ)), its only value must have support so we skip it. Now consider x1. Do its values have support? Changing ace (floor( x)) to occ( (min(x0 ), max(x1 ), ... , min(xn-1))) decreases the number of occurrences of min( xi) = 4 by 1, and increases the number of occurrences of max(x1 ) = 5 by 1. As min( xi) ~ a = 4, this upsets the lex ordering of the two oc­ currence vectors. We therefore prune all values in the domain of x1 larger than a. This leaves a single supported value, 4.

Now consider x2 · Changing occ(floor(x)) to occ( (min(xo), ... , max(x2), ... , min(Xn-d)) decreases the number of occurrences of min(x2) = 3 by 1, and increases the number of occurrences of max(x2) = 5 by 1. As with x1, any value of x2 larger than a = 4 upsets the lex ordering. We therefore prune 5 from the domain of x2. Now consider X3. Changing occ(floor(x)) to occ( (min(xo), . .. , max(x3), ... , min(xn-d)) decreases the number of occurrences of min(x3) = 2 by 1, and increases the number of occurrences of max(x3 ) = 4 by 1. The occurrence vectors beneath a would now be lex ordered the wrong way. We therefore also prune the value a = 4, leaving a single supported value 2 in the domain of x3. As x4 and x5 have singleton domains, their values have support.

Similarly, we check the minimums of the Yj for support. However, rather than prune values above (and in some cases equal to) a, there is now a dual pointer f3 and we prune values in the domains ofyj up to (and in some cases equal to) /3. The pointer f3 is the largest index such that the occurrence vectors beneath it are lex ordered the wrong way. Any value less than f3 cannot hope to change the lex ordering as the value at f3 will still order the vectors the wrong way. Such values can therefore be pruned. Once we have considered each ofthe yj, we have the following generalized arc-consistent vectors:

4.3 Algorithm details

The algorithm uses two pointers a and /3, and two flags 1 and o to avoid traversing the occurrence vectors each time we look for support. The pointer a is set to to the most significant index above which all occurrences are pair-wise equal and at a they are strictly ordered. If the vectors are equal then a is set to -oo. The pointer f3 is set to the most significant index below a such that the occurrence vectors are lex ordered the wrong way. If no such index exists, we set f3 to -oo. The flag 1 is set to true if all the indices between a and f3 are pair-wise equal and the flag o is set to true if the sub-vectors below f3 are lex ordered the wrong way. For example, given the occurrence vectors in section 4.2, a is set to 4, f3 to 2, and the flags 1 and o are set to true.

We summarise the major steps the algorithm performs:

1. Build ace (floor( x)) and occ( ceil(iJ))
2. Set a, /3, 1, o according to their definitions
3. For each xi: If its maximum disturbs the lex ordering on the occurrence vectors, tighten its upper-bound to a when the occurrence vectors are lex ordered below a, otherwise to a - 1.
4. For each y( If its minimum disturbs the lex ordering on the occurrence vectors, then tighten its lower-bound to f3 when the occurrence vectors are lex ordered below a, otherwise to f3 + 1.

When we prune a value, we do not need to check re­ cursively for previous support. Pruning changes neither the lower bounds of x nor the upper bounds of y. These values continue to provide support. The exception is when a domain is a singleton, and pruning causes a domain wipe-out.

We now give pseudo-code for an algorithm that maintains GAC on a multiset ordering constraint between vectors x and y which are of length n and m respectively. As the algorithm reasons about occurrences vectors, the original vectors need not be identical in length (though they often are).

The algorithm is called whenever lower bounds of xi or upper bounds of Yj change. Lines Al to A3 build the oc­ currence vectors ox and oy. Line Bl calls the procedure to set the pointers a and (3, and the flags 1 and J. Lines C113 check support for the maximums of the x; 's while lines D1-14 check support for the minimums of the y;'s.

Procedure GACMSOO

For each X;, we only check for support if x; is not singleton (line C2). There are six cases where we prune the domain of x;: (I) at line C4, as min(x;) 2 a, any value in the domain of x; greater than min(x;) lacks support because it will dis­ turb the lex ordering; (2) at line CS, as a > min(x;) > (3, and max(x;) 2 a, all the values in the domain of x; greater than a disturb the lex ordering, and lack support; (3) at line C6, C7, and C8, all values greater than or equal to a lack support. If we assign a to x;, then the vectors will be equal at index a and (3, the values between a and (3 are also all pair-wise equal (since 1 is true), and the vectors below (3 are ordered the wrong way (since J is true). Thus, the value a also lacks support and is pruned; (4) at line C9, all values greater than a lack support; (5) at line C10, Cll, and C12, all values greater than or equal to a lack support. If we assign a to x;, the vectors will be lex ordered the wrong way as the difference between the number of occurrences at a is exactly one, and 1 is true. Thus, the value a also lacks support and is pruned; (6) at line C13 all values greater than a lack support.

For each yj, we only check for support if Yj is not singleton (line D2). There are four cases where we prune the domain of Yj: (1) at line D4, as max(yj) > a, any value smaller than max(yj) disturbs the lex ordering and lacks support; (2) at lines DS to D8, the situation is dual to the third case for the x;, and any value less than or equal to (3 lacks support; (3) at line D9, any value less than (3 lacks support; ( 4) at line D 10, again, any value less than or equal to (3 lacks support.

4.4 Theoretical properties

In a longer technical report, we prove the following results about the algorithm's complexity and correctness.

Theorem 1 GACMSO runs in time O(n + m +d) where d is u -l.

If d « n, m (and for multisets, we expect this as the num­ ber of values is typically less than the cardinalities to permit repetition), then the algorithm is O(n + m).

Theorem 2 For disjoint and non-repeating vectors, GACMSO either establishes failure if x ~m y is not satisfiable, or prunes values from x and y to ensure GAC(x ~m if).

The algorithm can easily be modified to support strict mul­ tiset ordering. The only differences are that we fail if ox = oy and that (3 is set to l - 1 not -oo. The algorithm then en­ forces a strict inequality on the occurrence sub-vectors above (3. Another variant of the algorithm is when d » n, m. In such a situation, it could be costly to construct the occurrence vectors. We can instead sort the minimums of the x; and the maximums of the yj, and compute a, (3, 1 and J as if we had the occurrences by scanning these sorted lists. This information is all we need to compute support for each x; and Yj in tum. The complexity of this modified algorithm is 0( n log n + m log m) as the cost of sorting dominates.

If we have multiple rows of a matrix that are multiset or­ dered, we can decompose this into multiset ordering con­ straint on all pairs of rows, or (further still) onto ordering constraints just on neighbouring pairs of rows. The following result shows that such decompositions hinder constraint prop­ agation. Nevertheless, it will usually be most cost effective to post just the 0( n) ordering constraints between neighbouring pairs rather than the O(n 2 ) constraints between all pairs.

Theorem 3 GAC(Vi < j . x; ~m Xj) is strictly stronger than GAC(x; ~m xj)for all i < j, and this itself is strictly stronger than GAC(x; ~m xi+!) for all i.

5 Alternative approaches

5.1 Arithmetic constraint

Barbara Smith (personal communication) has proposed en­ forcing x <m y on vectors of length n via the arithmetic constraint nxo + ... nxn- 1 < nYo + ... nYn- 1 · This is similar to the transformation of a leximin fuzzy CSP into an equiva­ lent MAX CSP [Schiex et al., 1995]. BC on such a constraint is equivalent to GAC on the original multiset ordering con­ straint. However, such an arithmetic constraint is only feasi­ ble for small n. Further, most existing solvers will not enforce BC on such an arithmetic constraint, but will delay it until all but one of the variables are instantiated.

5.2 Decomposition

Multiset ordering is equivalent to the lex ordering the asso­ ciated occurrence vectors. As we have efficient algorithms for constructing occurrence vectors (via the global cardinal­ ity constraint [Regin, 1996]) and for lex ordering [Frisch et a/. , 2002], this might be an alternative approach. However, as the following theorem shows, such a decomposition hin­ ders constraint propagation. Also, the two global cardinality constraints in such a decomposition are more expensive to en­ force than the algorithm presented here. We write gcc(x, ox ) for the global cardinality constraint that channels from avec­ tor of variables x to the associated occurrence vector ox.

Theorem 4 GAC(x <m ff) is strictly stronger than simulta­ neously enforcing GAC(gcc(x, ox)) . GAC(gcc(y, oy)). and GAC(ox <lex oy).

Proof: Clearly it is as strong. To show strict­ ness, consider x = ({1, 2}, {1, 2} , {2}, {2}) and y = ( {1, 2}, {1, 2}, {0, 1, 2}, {0, 1} ). The multi set ordering con­ straint is not GAC since 0 in y2 has no support but the decom­ position is unable to determine this. QED.

Another approach is to use the sorted constraint in the Eclipse solver. This ensures that the values taken by one vec­ tor of variables are identical but in sorted order to the values taken by a second vector of variables. To post a multiset or­ dering constraint on two vectors, we can channel each into a sorted vector and lex order these. The above example demon­ strates that such a decomposition again hinders propagation. The sorting constraint is also more expensive to enforce.

6 Experimental results

We designed some experiments to test three goals. First, is multiset ordering an effective method for dealing with row and/or column symmetry? Second, how does multiset order­ ing compare to lex ordering? Which one breaks more sym­ metry? Is a combined method, which multiset orders one di­ mension and lex orders the other one of the matrix, superior? Third, does our GAC algorithm do more inference in prac­ tice than the decomposition? Similarly, is the algorithm more efficient in practice than its decomposition?

The symmetry breaking constraints we used are strict lex ordering on the columns (<lex C). on the rows ( <!exR); mul­ tiset ordering on the rows (:::;mR), (strict) multiset ordering on the columns (:::;mC and <mC); and combinations of these constraints. Such constraints are posted between adjacent rows/columns. The results of the experiments are shown in tables where a"-" means no result is obtained in 1 hour (3600 sees). The experiments are done using ILOG Solver 5.2 on a 1 OOOMHz pentium III with 256 Mb RAM using Windows XP.

6.1 Progressive Party Problem

There are a set of host boats, each with a capacity, and a set of guest boats, each with a crew size. We wish to assign a host for each guest and period, such that a guest crew never visits the same host twice, no two guest crews meet more than once, and the spare capacity of each host boat, after accommodating its own crew, is not exceeded (prob013 in csplib.org).

A matrix model of this problem [Smith eta/., 1995] is a 2-d matrix of guests x periods where each variable is as­ signed a host representing that a host is accommodating a particular guest in a given time period. The rows are the guests, the columns are the periods. This model has col­ umn and partial row symmetry: any two periods, and any two guests with the same crew size are indistinguishable. We consider the 13-hosts and 29 guests problem with 5 and 6 time periods, referred as 5-13-29 and 6-13-29. These prob­ lems have p!14!2!4!5!7! row and column symmetries where p is the number of time periods. The actual data can be found in csplib.org. Due to the problem constraints, no pair of rows/columns can be equal, hence we can safely pose strict lex ordering. However, any two distinct rows/columns might be equal when viewed as multisets.

As in [Smith eta/., 1995], the guest boats are ordered in descending order of their size. We order the host boats in descending order of spare capacity to choose a value in a succeed-first manner. Results obtained by row-by-row, and column-by-column labelling strategies are given in Tables 1 and 2. With row-by-row labelling, we cannot solve 6-13-29 with or without symmetry breaking. For the 5-13-29 problem, <!exR breaks a lot more row symmetry than :::;mR. However, the reverse is true for the columns. Here, <!exC does not break any symmetry but :::;mC does. Multiset ordering one dimension of a matrix therefore does not necessarily break less symmetry than lex ordering the same dimension. Such phenomena occur through interactions with the search strat­ egy: a search strategy might already lex order, so multiset ordering constraints break additional symmetry. The smallest search tree and also the least solving time is obtained by :::;m C <!exR. This supports our conjecture that lex ordering one di­ mension combined with multiset ordering the other can break more symmetry than lex/multiset ordering both dimensions.

With column-by-column labelling, we are able to solve the 6-13-29 problem. Neither of <!exR, <!exC, <!exRC break any symmetry. The smallest search tree is obtained by :::;m C. This supports our conjecture that multiset ordering one di­ mension can break more symmetry than lex ordering the same or both dimensions. If the search strategy already orders both dimensions lexicographically, imposing a constraint like mul­ tiset ordering in one dimension breaks additional symmetry.

6.2 Sports Scheduling with Odd Teams

This is a modified version ofprob026 in csplib.org. We have n teams (n is odd), playing over n weeks. Each week is divided into ( n - 1) /2 periods, and each period is divided into 2 slots, home and away. We wish to find a schedule so that every team plays at most once a week, every team plays twice in the same period over the tournament and every team plays every other team. We slightly modify the model in [Van Hentenryck et al., 1999], where teams is a 3-d matrix of periods x weeks x slots. Each element of teams is the team playing in a given period, week and slot. We treat this matrix as 2-d where the rows are the periods and columns are the weeks, and each entry is a list of variables giving the slots.

As the periods and the weeks are indistinguishable, this problem has n!(n- 1/2)! row and column symmetries. We pose strict ordering constraints on the rows and columns of teams as the periods and weeks cannot be equal. Due to the constraints on the periods, posing multiset ordering on the rows is not effective.

Results obtained by column-by-column labelling of the teams are given in Table 3. For one column, we first label the first slots; for the other, we first label the second slots. With this strategy, <texR does not break any symmetry, so we omit it in the table. Posing multiset ordering by our algo­ rithm is much more effective and efficient than by gee and lex ordering constraints. This holds for many other search strate­ gies. In Table 3, we note that <mC gives a smaller search tree than <texC. However, for other search strategies the reverse is true. This supports the theoretical result that lex ordering and multiset ordering are incomparable.

7 Conclusions

We have identified a new and important global (non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are or­ dered. We have developed an efficient linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. We have proposed a number of appli­ cations for this new constraint including breaking symmetry in matrix models, and fuzzy constraint satisfaction. We have shown that alternative methods for posting a multiset ordering constraint like an arithmetic constraint or decomposition are inferior. Finally, we have implemented this generalized arc­ consistency algorithm in ILOG Solver. Experimental results on a number of problem domains show considerable promise.