Ranking Constraints

1 Introduction

In many problems we want to reason about the ranking of items. For example, in information retrieval, we often want to aggregate several search results. The results being aggregated together may contain ties, and so are rank orders (e.g. [Fagin et al., 2004; Brancotte et al., 2015]). As a second example, we may wish to construct an overall ranking of tennis player based on pairwise comparisons between players. One principled method for constructing a ranking is the Kemeny distance [Kemeny, 1959; Levenglick, 1975] as this is the unique scheme that is neutral, consistent, and Condorcet. Unfortunately, determining this ranking is NP-hard, and remains so when we permit ties in the input or output [Hemaspaandra et al., 2005]. As a third example, as we discuss shortly, tasks in a scheduling problem may run in parallel, resulting in a ranking rather than a permutation of tasks.

In a ranking, unlike a permutation, we can have ties. Thus, 12225 is a ranking whilst 12345 is a permutation. To reason about permutations, we have some beautiful, efficient and effective global constraints. Regin [1994] proposed an O(n2d2 ) domain consistency propagator for permutations where n is the number of variables and d is their domain size. This work won the 2013 AAAI Classic Paper award. For

Ranking Constraints

Emmanuel Hebrard LAAS-CNRS

Toulouse, France George Katsirelos INRA

Toulouse, France

Toby Walsh

University of New South Wales Sydney, Australia

bound consistency, there is an even faster O(n logn) propagator [Ortiz et al., 2003]. Every constraint toolkit now provides propagators for permutation constraints. Surprisingly, ranking constraints are not yet supported in any toolkit. We tackle this weakness by proposing a global ranking constraint.

One very important application for rankings is in reasoning about the correlation between two sequences. For instance, in a vehicle routing problem, we might wish to have a large correlation between routes on consecutive days. In this way, drivers can "learn the routes", and customers can see a predictable face at a predictable time. A standard method in statistics to achieve such correlation is to minimize the distance between the ranking of stops in a route. On the other hand, there are also applications where we want routes to be uncorrelated. For example, in delivering cash to ATMs, we may wish routes to be highly uncorrelated. We therefore also propose some global correlation constraints.

2 Background

Constraint Satisfaction

A Constraint Satisfaction Problem (CSP) is a triple P = hX↪ D↪ Ci where X is a set of variables, D is a function from variables to sets of values and D(Xi) is the domain of Xi. An assignment σ(S) to S ✓ X is a function S ! [Xi2SD(Xi) such that σ(Xi) 2 D(Xi). C is a set of constraints. A constraint c is a pair hSc↪Rci where Sc ✓ X and Rc is a predicate over QXi2Sc D(Xi). If Rc is made true by σ(Sc), c is satisfied by σ. We seek a σ(X) that satisfies all constraints.

Let min(X) (max(X)) be the minimum (max.) value in D(X). A value v 2 D(Xi) is domain consistent (DC) in a constraint c if there is a σ(Sc) that satisfies c such that σ(Xi) = v and σ(Xj) 2 D(Xj)8Xj 2 Sc ∩ ¶Xi♦ and range consistent (RC) if σ(Xj) 2 [min(Xj)↪max(Xj)]8Xj 2 Sc ∩¶Xi♦. A constraint is DC (RC) if 8Xi 2 Sc↪ v 2 D(Xi), v is DC (RC). It is bound consistent (BC) if min(Xi) and max(Xi) are RC for all Xi 2 Sc. It is domain (range) disentailed if all values are domain (range) inconsistent.

A RANKING on a set of variables ensures an assignment is a ranking under some ordering of the variables.

Definition 1 A sequence R is a ranking (often called a standard ranking) iff either R = (1), or R = (x1↪ ▷ ▷ ▷ ↪ xm+1)

with xm+1 = xm or xm+1 = m + 1 and (x1↪ ▷ ▷ ▷ ↪ xm) is a ranking. RANKING(X1↪ ▷ ▷ ▷ ↪Xn) iff the sorted sequence (X⇡(1)↪ ▷ ▷ ▷ ↪X⇡(n)) is a ranking.

For example, RANKING([4↪ 1↪ 2↪ 2]) is satisfied but RANKING([3↪ 1↪ 4↪ 3]) is not.

Scheduling

In scheduling, we need to determine starting times for a set of tasks of a given duration, respecting their release and due dates, bounds on the utilization of resources, so that an objective like the makespan is minimized. In the "batching machine" model [Potts and Kovalyov, 2000], the resources (such as, for instance, an oven) have a capacity, but the processing time of the tasks scheduled in parallel equal the processing time of the longest task. In this model, the partial order on the equivalence classes "processed in parallel" is a ranking. In some scheduling problems the length of a task is time dependent [Gupta and Gupta, 1988], for instance because of a "learning curve" [Dutton and Thomas, 1984], or because of wear and tear, see [Biskup, 2008] for a survey. Some models relate the duration of a task to the number of times a similar task has been processed in the past [Biskup, 1999; Gordon et al., 2008]. In our experiments, we used the model of Mosheiov [2005], where the processing time of task i is ripi where pi is a constant and ri the rank of task i.

Correlation Constraints

Let X = ¶X1↪ ▷ ▷ ▷ ↪ Xn♦ and Y = ¶Y1↪ ▷ ▷ ▷ ↪ Yn♦ be two rankings. They are positively correlated if the distance between X and Y is low, negatively correlated if this distance is high and uncorrelated if this distance is average. Several distance measures can be used to define a correlation coefficient. In this paper, we consider only Manhattan distance, a well known correlation metric. We measure correlation using the Spearman's Footrule, a simple measure of correlation between sequences based on Manhattan distance. We denote m = j n2 4 k the median Manhattan distance between two rankings. If we consider the gap to the median ♣Pni=1 ♣Xi -Yi♣ -m♣, we can enforce uncorrelation by stating an upper bound, or correlation (either positive or negative) by stating a lower bound. This gives the following two global correlation constraints where ⊕ 2 ¶↪ ≥♦:

Definition 2

3 The Ranking Constraint

We introduce two decompositions for the RANKING constraint. The first uses the SORTEDNESS(X↪Y) constraint [Older et al., 1995], which ensures that Y is a sorted version of the sequence X and which is itself efficiently decomposable [Schaus, 2010]:

The second decomposition uses the GCC(X↪ V↪Y) constraint [Oplobedu et al., 1989], which ensures that each value v 2 V appears Yv times 1 in the sequence X:

Proposition 1 Neither encoding achieves BC

Proof: Consider X1↪X2 2 [1↪ 5]↪X3 = 4 and X4↪X5↪X6 2 [2↪ 3]. This instance does not admit a ranking. However neither decomposition identifies this. ⇤

We next show that domain consistency can be enforced in polynomial time. However, our propagator requires many (O(n2 )) calls to a min cost flow algorithm, so we also propose an efficient algorithm for reasoning with interval domains.

3.1 Domain Consistency

High level description. We reformulate the problem as a lexicographic maximum flow [Kozen, 2009], modeled using exponentially large costs. If the lex-max flow is not a ranking, we force a lexicographically smaller choice at the point where the ranking property is violated. Since there are only two choices at each point of the sorted sequence, the smaller choice is true in all solutions and will not be revisited, although previous choices may have to be revised. Hence, we make O(n2 ) revisions and get a polynomial runtime. We present this in Algorithm 1.

Construction. The construction is similar to that of nested GCC [Zanarini and Pesant, 2007] over the intervals [1↪ 1]↪ [1↪ 2]↪ ▷ ▷ ▷ ↪ [1↪ n]. There exists a unique source s and sink t, a vertex xi for each variable Xi and arcs (s↪ xi) with demand 1 and cost 0. There exists a vertex vj for each value j and an arc (xi↪ j) iff j 2 D(Xi). For each j 2 [1↪ n], there exists a vertex ivj for the interval [1↪ j] and an arc (vj↪ ivj) with cost nn-i+1 = 2(n-i+1) logn . For each j 2 [2↪ n] there is an arc (ivj-1↪ ivj) with demand j - 1. Finally, there is an arc (ivn↪ t) with demand n. Unless otherwise mentioned, all arcs have maximal capacity, no demand and no cost. We denote this network by N(X1↪ ▷ ▷ ▷ ↪ Xn).

1 The version where Y is a set of integer variables is called "extended" GCC in [Quimper, 2006].

Algorithm 1: DCSupport(X1↪ ▷ ▷ ▷ ↪ Xn)

G = N(X1↪ ▷ ▷ ▷ ↪Xn) ; while true do F =MinCostFlow(G↪ n) ; // n units of flow if There exists no flow then FAIL ; σ = ¶Xi = j ♣ F(xi↪ vj) > 0♦ ; if σ is a ranking then return σ ; o sort(σ) ; // by assigned value r first position in o that violates the ranking property ; p max¶j ♣ 9i↪ k s.t. o(k) = ¶Xi = j♦↪ k < r♦; set demand of arc (ivp↪ ivp+1) in G to r;

Theorem 1 Algorithm 1 returns a support of a RANKING constraint iff the constraint is satisfiable, in polynomial time.

Proof: ) Immediate.

( Consider a minimum cost feasible flow of G. In the usual way, we construct an assignment σ to the variables of the constraint. Let Z1↪ ▷ ▷ ▷ ↪ Zn be the sorted assignment, i.e., there exists a permutation ⇡ such that Zi = σ(X⇡(i)) and Zi  Zi+1 for all i 2 [1↪ n - 1]. This sequence has the property Z1 = 1, Zr 2 [Zr-1↪ r] for 2  r  n, otherwise the demand on (ivr-1↪ ivr) would be violated. This is weaker than the ranking property Z1 = 1, Zr 2 ¶Zr-1↪ r♦. Suppose Z1↪ ▷ ▷ ▷ ↪Zn is not a ranking. Then there exists a minimum r such that Z1↪ ▷ ▷ ▷ ↪Zr-1 = p is a ranking and Zr 2 (p↪ r). By construction, we place priority on higher values, hence no flow extends Z1↪ ▷ ▷ ▷ ↪ Zr-1 with Zr = r, nor is there a flow in which any of Zi↪ i  r gets a larger value. Hence, any ranking is lexicographically smaller than Z1↪ ▷ ▷ ▷ ↪Zr and if it matches Z1↪ ▷ ▷ ▷ ↪Zr-1 then Zr = p. This is enforced by requiring at least r values to be smaller than p, by setting the demand of the edge (ivp↪ ivp+1) to r.

Since the lexicographic upper bound of the flow is reduced at each iteration, the algorithm will eventually find a flow that is a ranking or report that none exists. In that case, the constraint is unsatisfiable, by the correctness of the bound. The demand of one of the n edges (ivi↪ ivi+1) is increased at each iteration and the total flow is n, so there are O(n2 ) iterations. The weights are represented with n log n bits, so computing the flow is polynomial, as is the entire algorithm. ⇤

Note that given the above algorithm we can achieve domain consistency by probing (see also section 5).

3.2 Bounds Consistency

Support. Algorithm 2 computes the lexicographically maximum BC support σ, if one exists, and fails otherwise. It maintains a partition of the variables into assigned (A) or unassigned (U). Suppose it extracts the variables in U in the order Xi1 ↪ ▷ ▷ ▷ ↪Xin . It always tries to assign to variable Xik the value k (line 2), while line 1 ensures that Xik has minimum upper bound among those that contain k or fails if no such variable exists. Construction of a ranking can continue either with the value k or ♣A♣ + 1 (= k + 1 in the first iteration of the loop at line 3). If some variables do not contain ♣A♣+1, it assigns them k (line 5). These are forced variables. This may create further forced variables. If the domain of a forced variable does not contain k either, it fails (line 5).

Algorithm 2: RCSupport(X1↪ ▷ ▷ ▷ ↪ Xn)

U ¶1↪ ▷ ▷ ▷ ↪ n♦; A ;; σ []; while U 6= ; do k ♣A♣ +1 ; 1 pop argmini♣k2D(Xi) (max(Xj)) from U or FAIL; 2 σ[i] k; A A[ ¶i♦; F ;; 3 while 9Xj 2 U s.t. max(Xj) < ♣A♣ +1 do F F [ ¶j ♣ j 2 U ^max(Xj) < ♣A♣ +1♦; U U ∩ F; A A[F; if ♣F♣ > 0 then 4 if 9j 2 F s.t. k ◁2 D(Xj) then FAIL; 5 else σ[F] k;

D(X1) = 1 2 D(X2) = 1 2 D(X3) = 1 2 3 D(X4) = 2 3 D(X5) = 1 2 3 4 D(X6) = 3 4 5 6 D(X7) = 2 3 4 5 6 7 D(X8) = 4 5 6 7 D(X9) = 4 5 6 7

Algorithm 2 orders the variables as given and finds the support marked in bold. X4, X5, X8 and X9 are forced.

Theorem 2 Algorithm 2 returns a valid BC support if one exists and fails otherwise, in time O(n log n)

Proof: Algorithm 2 constructs an assignment as well as a total variable ordering which agrees with the partial ordering where variables are ordered by their rank. The total order is given by the order in which variables are popped from A (for variables in M, we choose arbitrarily). We show that the algorithm constructs the lexicographically maximal among the non-decreasing solutions in this ordering if and only if the constraint has a bounds support.

()) This is straightforward.

(() Suppose the RANKING constraint has a bounds support but algorithm 2 fails. At the point where it fails, it has constructed a total ordering oa of a subset X0 ⇢ X = [X1↪ ▷ ▷ ▷ ↪Xn]. Now let σ1 be a bounds support of the constraint. We extend the partial order induced by the ranking of σ1 to a total order os arbitrarily and consider σmax, the lexicographically maximal among the solutions that are nondecreasing in the order os. For these total orders, we write o(i) to denote the variable in the ith position.

Since the algorithm failed without producing a solution, either oa disagrees with os or σ disagrees with σmax in X0 . We show that there exists an ordering and corresponding lexmax non-decreasing solution that do not disagree with oa and σ, a contradiction. We use induction on the position q of the first disagreement between either oa and os or σ and σmax.

Base case. For q = 1, the only possible value is 1, so the only possible disagreement is in the ordering. Let oa(1) = i, os(1) = j. Since Xi is chosen such that max(Xi) is minimum, it follows σ(i) ≥ max(Xj). Thus we can swap Xi and Xj in the ordering and in σ and get a new ordering o0s and assignment σ0max that agree with oa and σ at position 1.

(1) Suppose first that oa(q) = os(q) = i but σ(i) 6= σmax(i). Observe that the ranking os(1) ▷ ▷ ▷ os(q - 1) can be only be extended by p = σmax(os(q -1)) (i.e., continue a sequence of p ranks, σmax(i) = p) or by q > p. Algorithm 2 chooses σ(i) = q, so it follows that σmax(i) = p. Let r ≥ q be the greatest index such that σmax(os(r)) = p and hence by the above reasoning σmax(os(r+1)) = r+1. For all variables Xj ↪ j 2 [omax(q +1)↪ omax(r)], it must be min(Xj)  p < q and max(Xj) ≥ q, otherwise they would have been chosen before Xi by algorithm 2, which is impossible since oa and os agree until position q. Hence we can construct σ0max (j) = σmax(j) if j ◁2 [q↪ r] and q otherwise. In other words we transform the ranking (1↪ ▷ ▷ ▷ ↪ p↪ ▷ ▷ ▷ ↪ p ↪ r + 1↪ ▷ ▷ ▷)

Inductive step. Assume now that oa and σ agree with os and σmax until the q - 1th position.

σ0max is a ranking, non-decreasing over os and lexicographically greater than σmax, a contradiction.

(2) Suppose oa disagrees with os at position q so that oa(q) = i and os(q) = j but σ(i) = σmax(j). As in the base case (q = 1), we can swap i and j in σmax and os to get σ0max and o0s that agree with σ and oa.

(3) Finally, assume oa(q) = i↪ os(q) = j 6= i and σ(i) 6= σmax(j). By the argument in case (1), σmax cannot be a lexicographically maximal solution over os.

Complexity. In each iteration we assign at least one variable, hence the loop runs O(n) times. All operations are in O(1), except line 1, which is in O(log n) using a binary heap, for a total O(n log n). ⇤

Probing propagator

Based on algorithm 2, we can enforce range consistency on a RANKING constraint by "probing", i.e., asserting for each v 2 D(Xi) Xi = v and looking for a bound support. If none exists, that value is pruned. The cost of this is O(n3 logn), as it runs algorithm 2 once for each value in each domain. Hence, we explore computationally cheaper alternatives.

Pruning Conditions.

We first identify the conditions under which algorithm 2 can fail and for when a value is range inconsistent.

Definition 3 ((super-)Hall intervals) Let Vv(a↪ b) = ¶X ♣ D(X) ✓ [a↪ b]♦ and S(a↪ b) = ♣Vv(a↪ b)♣. We say that [a↪ b] is a Hall interval if S(a↪ b) = b - a + 1 and a super-Hall interval if S(a↪ b) > b - a + 1. We write ∆(a↪ b) = [b + 1↪ a + S(a↪ b) - 1], ∆(a↪ b) = [b + 1↪ a + S(a↪ b)].

Lemma 1 If a ranking constraint contains a super-Hall interval [a↪ b], then 8Xi 2 X, Xi ◁2 ∆(a↪ b). Moreover, if [a↪ b] is a Hall interval, then 8Xi 2 X ∩ Vv(a↪ b), Xi 2 [a↪ b] ! 8Xj 2 X▷Xj ◁2 ∆(a↪ b).

Proof: Suppose there exists a ranking that violates this condition, i.e., 9Xi 2 ∆(a↪ b). Since min(∆(a↪ b)) = b + 1, every variable in Vv(a↪ b) is ranked strictly higher than Xi, and the lowest possible rank among them is a. So the value assigned to Xi must be at least a + S(a↪ b).

For the second claim, if the left hand side is satisfied, S(a↪ b) increases, making it equivalent to the first claim. ⇤

The first condition is also correct for Hall intervals, but ∆(a↪ b) = [b + 1↪ a + S(a↪ b) - 1] = [b + 1↪ a + b - a] = ;, so we achieve no pruning.

Example 2 Consider again the instance RANKING ([X1↪ ▷ ▷ ▷ ↪X9]) from Example 1. The interval [1↪ 2] is a Hall interval with Vv(1↪ 2) = ¶X1↪X2♦. The interval [1↪ 3] is a super-Hall interval with Vv(1↪ 3) = ¶X1↪X2↪X3↪X4♦ and entails that [4↪ 4] is inconsistent for all variables.

Definition 4 (Saturated/Failed value) A value v such that v = ♣Vu(1↪ v)♣, where Vu(1↪ v) = ¶Xi ♣ min(Xi)  v♦, is called a saturated value. It is a failed value if v > ♣Vu(1↪ v)♣.

Lemma 2 If a RANKING constraint contains a failed value it is unsatisfiable. If it contains a saturated value v, then in every solution σ, σ(Xi)  v↪ 8Xi 2 Vu(1↪ v).

Proof: The first claim follows from the fact that in a ranking the kth value is at most k, but when there exists a failed value v, if Xj is at position ♣Vu(1↪ v)♣ + 1  v, [1↪ v] ◁2 D(Xj). The second claim follows because if we made any of these assignments, v would become a failed value. ⇤

Theorem 3 A RANKING constraint is bounds disentailed if and only if either (a) the constraint contains a failed value; or (b) The constraint contains a variable X and a set S of super-Hall intervals such that dom(X) ✓ [[a↪b]2S∆(a↪ b).

)By theorem 2 it suffices to show this for algorithm 2.

Proof: (. This follows from lemmas 1 and 2.

Algorithm 2 fails only in lines 1 and 4. In the first case (line 1), k is failed value. Indeed, k - 1 = n - ♣A♣ variables have been assigned and none of the remaining variables contain k, hence their lower bound is greater than k. So ♣vars(k)♣ = k - 1 and k is a failed value.

We have that b < k because Xk 2 F and, because Xi was not forced, i < j and a = i. For all Xp↪ i  p < j, we have that maxXp  b as well. If not, suppose p is the greatest index such that maxXp > b. Since maxXp+1  b and Xp is chosen before Xp+1, it must be because Xp gets a value v which is not in the domain of Xp+1. It also means that Xp+1 gets v + 1 = minXp+1 and is unforced, contrary to the assumption that Xi is the latest such variable. Hence, ¶Xi↪ ▷ ▷ ▷ ↪ Xk♦ ✓ Vv(a↪ b). Moreover, we have ♣[a↪ b]♣ = b - a + 1 < k - i + 1 = ♣¶Xi↪ ▷ ▷ ▷ ↪ Xk♦♣  ♣Vv(a↪ b)♣, proving that [a↪ b] is a super-Hall interval. Hence the values that the algorithm skips when constructing a support are exactly those that are in ∆(a↪ b) of some super-Hall interval [a↪ b].

For the second case (line 4), the algorithm fails because a variable Xj is in F but does not contain the value k, so maxXj < k. Assume w.l.o.g. that the variables are chosen in the order X1↪ ▷ ▷ ▷ ↪ Xn. We claim that each time F 6= ;, the algorithm has identified a super-Hall set. We say that a variable assigned in line 5 is forced. Let F = ¶Xj↪ ▷ ▷ ▷ ↪Xk♦ and Xi be the latest unforced variable with σ(Xi) = min(Xi). (X1 in the extreme). Then we show that the interval [a↪ b] where a = minXi and b = maxp2M D(Xp) is a super-Hall interval and Vv(a↪ b) = ¶Xi↪ ▷ ▷ ▷ ↪ Xk♦.

Consider now the failed variable Xj . Suppose algorithm 2 has used a value in D(Xj) and let v be the largest one. When it used v, Xj would be in F and it would be assigned v, which did not happen. Hence, algorithm 2 has skipped over all of D(Xj), so there exists a series of super-Hall intervals whose ∆(a↪ b) cover D(Xj), as required. ⇤

Lemma 3 An assignment Xi = v is range inconsistent in RANKING constraint C if and only if (a) There exists a superHall interval [a↪ b] s.t. v 2 ∆(a↪ b); or (b) The constraint contains a saturated value v0 < v and Xi 2 Vu(1↪ v0 ); or (c) The constraint contains a variable Xj and two sets of Hall intervals S1↪ S2 such that 8[a↪ b] 2 S1↪ v 2 [a↪ b]^Xi ◁2 Vv(a↪ b), and dom(Xj ) ✓ ([[a↪b]2S1 ∆(a↪ b)) S ([[a↪b]2S2 ∆(a↪ b)).

Proof:[Sketch] (. This is immediate by lemmas 1 and 2. ). We examine the constraint C ♣Xi=v which is range disentailed and derive the above conditions. ⇤

The third condition means that there exists Xj whose values are either range inconsistent by super-Hall intervals in S2 or incompatible with Xi = v by Hall intervals in S1.

Filtering Algorithm

From Lemma 3 we can design an algorithm to enforce range consistency (RC), but its cost is similar to that of the probing propagator, so we propose an incomplete method instead.

Saturated values. We iterate over the variables sorted by non-decreasing upper bounds. Since the upper bound is n, sorting is in O(n) [Cormen et al., 2009, Chapter 8.2]. At step j we explore Xij , and if min(Xij ) ≥ j then ♣Vu(1↪ j -1)♣  j - 1, so j - 1 is failed (for strict inequality) or saturated, in which case we prune the upper bounds of Vu(1↪ j - 1).

Super-Hall intervals. The second type of pruning comes from super-Hall intervals, i.e., if [a↪ b] is such that S(a↪ b) > b - a + 1, then no variable can take a value in the interval [b + 1↪ a + S(a↪ b) - 1]. This can be achieved by computing all left-maximal Hall intervals as described in [Ortiz et al., 2003] with the difference that we continue when a Hall interval becomes a "super-Hall interval". This algorithm runs in O(n logn) and returns O(n) left-maximal Hall intervals. It explores the variables ordered by non-decreasing upper bound. For convenience, let Xi be the i-th such variable. We maintain at each step i, and for the lower bound a of each leftmaximal interval, the value of S(a↪ b) where b is max(Xi).

Definition 5 An interval [a,b] is left-maximal if there does not exist a value a0 such that S(a0 ↪ b) ≥ S(a↪ b) + a - a0 .

Notice that if [a↪ b] is not left-maximal because of [a0 ↪ b]↪ a0 < a any subsequent Hall interval [a↪ c]↪ c > b is also not left-maximal because of [a0 ↪ c]. Lemma 4 shows that the pruning due to non-left-maximal super-Hall intervals is subsumed by left-maximal Hall intervals.

Lemma 4 If the super-Hall interval [a↪ b] is not left-maximal but [a0 ↪ b] is then ∆(a↪ b) ✓ ∆(a0 ↪ b).

Therefore, we do not need to keep a as a possible lower bound for a future Hall interval and we can use the algorithm described by Ortiz et al. (2003). However, we continue to maintain a value S(a↪ b) even when it is strictly larger

Proof: By definition, we have S(a0 ↪ b) ≥ S(a↪ b) + a - a0 hence a0 + S(a0 ↪ b) ≥ a + S(a↪ b). ⇤

than a - b + 1, instead of pruning. When we move to the next variable Xi+1, if max(Xi+1) = max(Xi) we increment S(a↪max(Xi)) and add [a↪max(Xi)] to a list otherwise.

Backward pruning from (super-)Hall intervals. To enforce the pruning corresponding to case (c) in Lemma 3, we want to find a variable X whose domain is included into the union of ∆(a↪ b) for some intervals [a↪ b]. As shown in Lemma 1, if a variable Y whose domain is not contained in the union of those intervals takes a value in their intersection, then as ∆(a↪ b) increases, it will wipe out the domain of X. The values in the intersection are thus inconsistent for Y .

We give a O(n2 ) algorithm to achieve this with respect to every subset of left-maximal Hall intervals. However, one can prune even with respect to non left-maximal Hall intervals, this algorithm is therefore not complete.

We can make the two following simple observations:

Lemma 5 There are O(n) left-maximal (super-)Hall intervals, each with a distinct upper bound.

Proof: Consider two left-maximal intervals [a↪ b] and [a0 ↪ b] with a0 > a. Then by definition there exists no value a00 such that S(a00 ↪ b) ≥ S(a0 ↪ b) + a0 - a00 . But a00 = a is exactly such a value, a contradiction. ⇤

Lemma 6 If j > i then either ai ≥ aj or aj > bi.

Proof: Suppose that ai < aj and aj  bi. By Lemma 5, [ai↪ bi] is the unique left-maximal (super-)Hall interval with upper bound bi, so [aj↪ bi] is not left-maximal. Therefore, at least ai - aj variables have their domain in [ai↪ bi] and overlapping [ai↪ aj - 1]. Since these variables are also in [ai↪ bj], it is left maximal and [aj↪ bj] is not, a contradiction. ⇤

These observations allow to speed up the pruning. By Lemma 5, we know that the (super-)Hall intervals [aj↪ bj] for j 2 [1↪m] are ordered by upper bounds. Therefore, the intervals ∆(aj↪ bj) are ordered both by lower and upper bounds (since they are left-maximal). We explore variables by nondecreasing lower bound and find, at step i, the greatest l and smallest u such that D(Xi) 2 Suj=l ∆(aj↪ bj), and continue otherwise. When we find such a set, we can prune the intersection of the Hall intervals from the domain of any variable whose domain is not included in their union.

Finding l such that min(Xi) 2 ∆(aj↪ bj) can be done in logarithmic time by binary search (similarly for u). Then, by Lemma 6 there are two cases: Either au > bl and then the intervals [al↪ bl] and [au↪ bu] are disjoint, which means that there is no possible pruning, or au  al. However, we know by Lemma 5 that bu > bl. Therefore [al↪ bl] ✓↪ ▷ ▷ ▷ ↪✓ [au↪ bu]. Computing the intersection or the union can thus be done in constant time: the union is [au↪ bu] and the intersection [al↪ bl]. Thus, this takes O(n logn) time. However, we need O(n2 ) time to actually achieve the pruning. At step i we review every variable to check if its domain is contained in [au↪ bu] and not disjoint to [lb↪ ub], and if so, keep a memory of this pruning. After processing every variable, we actually perform the stored pruning in O(n2 ).

4 Experimental Evaluation

Here we compare our propagator for the RANKING constraint against the probing RC algorithm and the two decompositions. We used Choco 3 to implement the two propagators as well as the decompositions and we ran all the experiments on a cluster of AMD opteron 6176 2.3 GHz processors.

Choco 3 uses the algorithm of Mehlhorn and Thiel (2000) to propagate the SORTEDNESS constraint and an unspecified algorithm to propagate the GCC constraint.

Correlation and Uncorrelation. First, we considered the problem of minimizing the correlation between two vectors of variables X and Y using the RANKING CORRELATION constraint described in Section 2. We generated random ranges for all variables using two methods. First, we randomly picked two integers in [1↪ n] for every variable and used these as bounds. As this method may produce unsatisfiable instances, we also used a second method, where we first generate a ranking r as follows: r[1] = 1, and for i > 1, we set r[i] = r[i - 1] with probability 12 and r[i] = i otherwise. Then for every variable Xi we set its bounds to a random interval that includes r[i]. We used lexicographic variable ordering and branched on the minimum value in all cases, so the same search tree is explored, modulo pruning.

For every value of n in [5↪ 20], we generated 1000 random instances, and solved them with each method with a 30 minute time limit. Figure 2 shows the total runtime spent by the different methods for random intervals on each set of instances. The gain from the extra pruning is very clear (notice the logarithmic scale). At the end of the scale, the methods with weaker pruning cannot solve a significant proportion of the instance (dashed lines show the number of instances for which the time limit was reached). As a consequence, the gap in runtime is underestimated for the larger instances. The decomposition with SORTEDNESS seems to dominate (by orders of magnitude) the decomposition with GCC in this case.

Figure 3 shows results on instances with a solution embedded. The gain from stronger filtering is not as significant, but our propagator is still at least one order of magnitude faster than the decompositions. Interestingly, the relative performance of the decompositions is inversed here.

Scheduling. We also considered an application of the RANKING constraints to scheduling problems in the batching machine model with wear and tear. We generate such scheduling problems following the model of Mosheiov [Mosheiov, 2005]. For a number of tasks ranging from n = 5 to 10, we generate 50 such scheduling instances, choosing duration constants pi and demand at random. Then we post a CUMULATIVE constraint, as well as the channeling constraints between overlap and ranking and between ranking and actual durations ripi. The runtimes, in seconds, to solve each set of 50 instances are reported in Table 1, in the last column we also report the number of instances of size 10 that timed out after 3h. This problem is very hard for Choco, as only small problems can be tackled, but using our propagator improves scalability. In contrast to the uncorrelation problem, here the cost of propagating RANKING is small compared to the rest of the constraints, so the impact of the cost of the probing propagator is small. However, it remains measurably slower, suggesting that the extra pruning it may generate does not offset its higher computational cost. Once again, the two decompositions are worse than both propagators.

5 Conclusions

We have proposed a global ranking constraint. We argued that simple decompositions of this global constraint hurt pruning. We proposed instead some efficient filtering algorithms. One application for such propagators is ensuring two sequences are correlated or uncorrelated. To demonstrate the promise of these methods, we ran experiments on two problem domains and observed significant speedups compared to the decompositions.