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 A1 to A3 build the occurrence vectors ~ox and ~oy. Line B1 calls the procedure to set the pointers α and β, and the flags γ and δ. Lines C113 check support for the maximums of the xi's while lines D1-14 check support for the minimums of the yi's.

Procedure GACMSO()
A1. l := min({min(xi)|i ∈ [0, n)} ∪ {min(yj )|j ∈ [0, m)})
A2. u := max({max(xi)|i ∈ [0, n)} ∪ {max(yj )|j ∈ [0, m)})
A3. ~ox = occ(*floor*(~x)), ~oy = occ(*ceil*(~y))
B1. SetPointers-and-Flags(**l, u**)
C1. FOR i = 0 TO n − 1 % check support for x's C2. IF (min(xi) 6= max(xi)) C3. a := min(xi) b := max(xi)
C4. IF (a ≥ α) NC(xi = a)
C5. IF (**α > a > β** & b ≥ α) NC(xi ≤ α)
C6. IF (a = β & b ≥ α)
C7. IF (oxα **+ 1 =** oyα) C8. IF (γ & oxβ − 1 = oyβ & δ) NC(xi < α)
C9. **ELSE** NC(xi ≤ α)
C10. IF (**a < β** & b ≥ α)
C11. IF (oxα **+ 1 =** oyα) C12. IF (γ) NC(xi < α) C13. **ELSE** NC(xi ≤ α)
D1. FOR j = 0 TO m − 1 % check support for y's D2. IF (min(yj ) 6= max(yj)) D3. a := min(yj ) b := max(yj) D4. IF (**b > α**) NC(yj = b) D5. IF (b = α & oxα **+ 1 =** oyα)
D6. IF(a ≤ β & γ)
D7. IF (oxβ = oyβ + 1)
D8. IF (δ)NC(yj > β)
D9. **ELSE** NC(yj ≥ β) D10. ELSE NC(yj > β)
Procedure SetPointers-and-Flags(l, u)
B1. γ := false, δ := *false*, α := u B2. **WHILE** (α ≥ l ∧ oxα = oyα) α := α − 1 B3. IF (α ≥ l ∧ oxα > oyα) **FAIL**
B4. IF (α = l − 1) α := −∞, β := −∞
B5. **ELSE**
B6. β := α − 1, γ :=*true* B7. **WHILE** (β ≥ l ∧ oxβ ≤ oyβ) B8. IF (oxβ **< oy**β) γ := *false* B9. β := β − 1 B10. IF (β = l − 1) β := −∞, γ := *false* B11. IF (β 6= −∞ ∧ **β > l**)
B12. i := β − 1 B13. **WHILE** (i ≥ l ∧ oxi = oyi) i := i − 1 B14. IF (i ≥ l ∧ oxi **> oy**i) δ := *true* For each xi, we only check for support if xiis not singleton
(line C2). There are six cases where we prune the domain of xi: (1) at line C4, as min(xi) ≥ α, any value in the domain of xi greater than min(xi) lacks support because it will disturb the lex ordering; (2) at line C5, as α > min(xi) > β, and max(xi) ≥ α, all the values in the domain of xi greater than α disturb the lex ordering, and lack support; (3) at line C6, C7, and C8, all values greater than or equal to α lack support. If we assign α to xi, then the vectors will be equal at index α and β, the values between α and β are also all pair-wise equal (since γ is true), and the vectors below β are ordered the wrong way (since δ is true). Thus, the value α also lacks support and is pruned; (4) at line C9, all values greater than α lack support; (5) at line C10, C11, and C12, all values greater than or equal to α lack support. If we assign α to xi, the vectors will be lex ordered the wrong way as the difference between the number of occurrences at α is exactly one, and γ is true. Thus, the value α also lacks support and is pruned; (6) at line C13 all values greater than α 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 ) > α, any value smaller than max(yj ) disturbs the lex ordering and lacks support; (2) at lines D5 to D8, the situation is dual to the third case for the xi, and any value less than or equal to β lacks support; (3) at line D9, any value less than β lacks support; (4) at line D10, again, any value less than or equal to β 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 number 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 ~y).

The algorithm can easily be modified to support strict multiset ordering. The only differences are that we fail if ~ox = ~oy and that β is set to l − 1 not −∞. The algorithm then enforces a strict inequality on the occurrence sub-vectors above β. 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 xi and the maximums of the yj , and compute α, β, γ and δ as if we had the occurrences by scanning these sorted lists. This information is all we need to compute support for each xi and yj in turn. The complexity of this modified algorithm is O(n log n + m log m) as the cost of sorting dominates.

If we have multiple rows of a matrix that are multiset ordered, we can decompose this into multiset ordering constraint 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 propagation. Nevertheless, it will usually be most cost effective to post just the O(n) ordering constraints between neighbouring pairs rather than the O(n 2) constraints between all pairs.

Theorem 3 GAC(∀**i < j . ~x**i ≤m ~xj ) is strictly stronger than GAC(~xi ≤m ~xj ) *for all* **i < j***, and this itself is strictly* stronger than GAC(~xi ≤m ~xi+1) *for all* i.