# ranking_constraints__4db8155e.pdf

Ranking Constraints

Christian Bessiere

LIRMM-CNRS Montpellier, France

Emmanuel Hebrard

LAAS-CNRS Toulouse, France

George Katsirelos

INRA Toulouse, France

Zeynep Kiziltan Universit di Bologna

Bologna, Italy

Toby Walsh University of New South Wales

Sydney, Australia

We need to reason about rankings of objects in a wide variety of domains including information retrieval, sports tournaments, bibliometrics, and statistics. We propose a global constraint therefore for modeling rankings. One important application for rankings is in reasoning about the correlation or uncorrelation between sequences. For example, we might wish to have consecutive delivery schedules correlated to make it easier for clients and employees, or uncorrelated to avoid predictability and complacence. We therefore also consider global correlation constraints between rankings. For both ranking and correlation constraints, we propose efﬁcient ﬁltering algorithms and decompositions, and report experimental results demonstrating the promise of our proposed approach.

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, efﬁcient 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

bound consistency, there is an even faster O(n log n) 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 = h X, 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 h Sc, Rci where Sc X and Rc is a predicate over Q

Xi2Sc D(Xi). If Rc is made true by σ(Sc), c is satisﬁed by σ. We seek a σ(X) that satisﬁes 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 satisﬁes 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.

Deﬁnition 1 A sequence R is a ranking (often called a standard ranking) iff either R = (1), or R = (x1, . . . , xm+1)

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

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 satisﬁed 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 deﬁne a correlation coefﬁcient. 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 =

the median Manhattan distance between two rankings. If we consider the gap to the median |Pn

i=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 { , }: Deﬁnition 2

RANKINGCORRELATION (X, Y, C) () %%%%%

%%%%% C&RANKING(X)&RANKING(Y)

3 The Ranking Constraint We introduce two decompositions for the RANKING constraint. The ﬁrst 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 efﬁciently decomposable [Schaus, 2010]:

SORTEDNESS(X, Y), Y1 = 1 Yi = Yi 1 _ Yi = i 8i 2 [2, n]

([0, n], 44)

([0, n], 43)

([0, n], 42)

([0, n], 41)

([1, n], 0)

([2, n], 0)

([3, n], 0)

([4, n], 0)

Figure 1: Network ﬂow for a ranking with 4 variables. Arcs are labelled with ([demand, capacity], cost), or (demand, cost) if demand = capacity.

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

GCC(X, {1, . . . , n}, Y), Y1 = Z1 Zi = Zi 1 + Yi 8i 2 [2, n] Zi i 8i 2 [1, n] Yi = 0 () Zi 1 i 8i 2 [2, n]

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 identiﬁes 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 ﬂow algorithm, so we also propose an efﬁcient algorithm for reasoning with interval domains.

3.1 Domain Consistency High level description. We reformulate the problem as a lexicographic maximum ﬂow [Kozen, 2009], modeled using exponentially large costs. If the lex-max ﬂow 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) log n. 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).

1The 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 = Min Cost Flow(G, n) ; // n units of flow if There exists no ﬂow then FAIL ; σ = {Xi = j | F(xi, vj) > 0} ; if σ is a ranking then return σ ; o sort(σ) ; // by assigned value r ﬁrst 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 satisﬁable, in polynomial time.

Proof: ) Immediate. ( Consider a minimum cost feasible ﬂow 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 ﬂow extends Z1, . . . , Zr 1 with Zr = r, nor is there a ﬂow 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 ﬂow is reduced at each iteration, the algorithm will eventually ﬁnd a ﬂow that is a ranking or report that none exists. In that case, the constraint is unsatisﬁable, 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 ﬂow is n, so there are O(n2) iterations. The weights are represented with n log n bits, so computing the ﬂow 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 ﬁrst 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 arg mini|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;

Example 1 Consider the domains

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 ﬁnds 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 ﬁrst 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 o0

assignment σ0

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

(1) Suppose ﬁrst 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 σ0

max(j) = σmax(j) if j /2 [q, r] and q otherwise. In other words we transform the ranking (1, . . . , p, . . . , p | {z } 1...r

, r + 1, . . .)

to (1, . . . , p, . . . , p | {z } 1...q 1

, q, . . . , q | {z }

, r + 1, . . .). The new assignment

max 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 σ0

s 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 log n), as it runs algorithm 2 once for each value in each domain. Hence, we explore computationally cheaper alternatives.

Pruning Conditions. We ﬁrst identify the conditions under which algorithm 2 can fail and for when a value is range inconsistent.

Deﬁnition 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 satisﬁed, S(a, b) increases, making it equivalent to the ﬁrst claim. The ﬁrst 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.

Deﬁnition 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 unsatisﬁable. If it contains a saturated value v, then in every solution σ, σ(Xi) v, 8Xi 2 Vu(1, v).

Proof: The ﬁrst 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).

Proof: (. This follows from lemmas 1 and 2. ) By theorem 2 it sufﬁces to show this for algorithm 2. Algorithm 2 fails only in lines 1 and 4. In the ﬁrst 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.

For the second case (line 4), the algorithm fails because a variable Xj is in F but does not contain the value k, so max Xj < 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 identiﬁed 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 = min Xi and b = maxp2M D(Xp) is a super-Hall interval and Vv(a, b) = {Xi, . . . , Xk}.

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 max Xp b as well. If not, suppose p is the greatest index such that max Xp > b. Since max Xp+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 = min Xp+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].

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 super Hall 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)

[[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 log n) 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). Deﬁnition 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).

Proof: By deﬁnition, we have S(a0, b) S(a, b) + a a0 hence a0 + S(a0, b) a + S(a, 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

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 ﬁnd 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 deﬁnition 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 ﬁnd, at step i, the greatest l and smallest u such that D(Xi) 2 Su

j=l (aj, bj), and continue otherwise. When we ﬁnd 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 log n) 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).

Figure 2: Uncorrelation: Random uniform intervals

Figure 3: Uncorrelation: Solution embedded

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 unspeciﬁed 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 unsatisﬁable instances, we also used a second method, where we ﬁrst generate a ranking r as follows: r[1] = 1, and for i > 1, we set r[i] = r[i 1] with probability 1

2 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 signiﬁcant 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 ﬁltering is not as signiﬁcant, 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.

Table 1: Scheduling: Total runtime in seconds

size: 5 6 7 8 9 10 #U propagator 97 359 1203 3795 29302 275237 14 probing 73 371 1428 4721 33975 276240 15 GCC 106 432 1389 4936 54495 323433 19 SORTEDNESS 104 458 1509 6118 65445 328331 17

5 Conclusions

We have proposed a global ranking constraint. We argued that simple decompositions of this global constraint hurt pruning. We proposed instead some efﬁcient ﬁltering 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 signiﬁcant speedups compared to the decompositions.

[Biskup, 1999] Dirk Biskup. Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1):173 178, 1999. [Biskup, 2008] Dirk Biskup. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2):315 329, 2008. [Brancotte et al., 2015] Bryan Brancotte, Bo Yang, Guil-

laume Blin, Alain Denise Sarah Cohen-Boulakia, and Sylvie Hamel. Rank aggregation with ties: Experiments and analysis. Proceedings of the VLDB Endowment (PVLDB), 2015. [Cormen et al., 2009] Thomas H. Cormen, Charles E. Leis-

erson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. [Dutton and Thomas, 1984] John M. Dutton and Annie

Thomas. Treating Progress Functions as a Managerial Opportunity. The Academy of Management Review, 9(2):235 247, April 1984. [Fagin et al., 2004] Ronald Fagin, Ravi Kumar, Mohammad

Mahdian, D. Sivakumar, and Erik Vee. Comparing and aggregating rankings with ties. In Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 04, pages 47 58, New York, NY, USA, 2004. ACM. [Gordon et al., 2008] V. S. Gordon, C. N. Potts, V. A. Stru-

sevich, and J. D. Whitehead. Single machine scheduling models with deterioration andlearning: handling precedence constraints viaprioritygeneration. Journal of Scheduling, 11(5):357 370, 2008. [Gupta and Gupta, 1988] Jatinder N.D. Gupta and Sushil K.

Gupta. Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14(4):387 393, 1988. [Hemaspaandra et al., 2005] Edith Hemaspaandra, Holger

Spakowski, and Jrg Vogel. The complexity of kemeny elections. Theoretical Computer Science, 349(3):382 391, 2005. [Kemeny, 1959] John G Kemeny. Mathematics without numbers. Daedalus, 88(4):577 591, 1959. [Kozen, 2009] Dexter Kozen. Lexicographic ﬂow. Technical

Report http://hdl.handle.net/1813/13018, Computing and Information Science, Cornell University, June 2009. [Levenglick, 1975] Arthur Levenglick. Fair and reasonable

election systems. Behavioral Science, 20(1):34 46, 1975. [Mehlhorn and Thiel, 2000] Kurt Mehlhorn and Sven Thiel.

Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint. In Principles and Practice of Constraint Programming CP 2000, pages 306 319. Springer, 2000. [Mosheiov, 2005] Gur Mosheiov. A note on scheduling de-

teriorating jobs. Mathematical and Computer Modelling, 41(89):883 886, 2005.

[Older et al., 1995] W.J. Older, G.M. Swinkels, and M.H.

van Emden. Getting to the real problem: experience with BNR Prolog in OR. In Proceedings of the Third Conference on Practical Applications of Prolog, pages 465 478, 1995. [Oplobedu et al., 1989] A. Oplobedu, J. Marcovitch, and

Y. Tourbier. CHARME: Un langage industriel de programmation par contraintes, illustr e par une application chez Renault. In Ninth International Workshop on Expert Systems and their Applications: General Conference, volume 1, pages 55 70, 1989. [Ortiz et al., 2003] Alejandro Ortiz, Claude-Guy Quimper,

John Tromp, and Peter van Beek. A fast and simple algorithm for bounds consistency of the alldifferent constraint. In Proceedings of the 18th International Joint Conference on Artiﬁcial Intelligence, pages 245 250, Acapulco, Mexico, 2003. [Potts and Kovalyov, 2000] Chris N. Potts and Mikhail Y.

Kovalyov. Scheduling with batching: A review. European Journal of Operational Research, 120(2):228 249, 2000. [Quimper, 2006] Claude-Guy Quimper. Efﬁcient propagators for global constraints. Ph D thesis, University of Waterloo, 2006. [R egin, 1994] Jean-Charles R egin. A ﬁltering algorithm for

constraints of difference in CSPs. In Proceedings of the 12th National Conference on AI, pages 362 367. AAAI, 1994. [Schaus, 2010] Pierre Schaus. http://cp-isfun.blogspot.com/2010/09/recent-trend-of-cp-that-inoticed-is.html, 2010. [Zanarini and Pesant, 2007] Alessandro Zanarini and Gilles

Pesant. Generalizations of the global cardinality constraint for hierarchical resources. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR), pages 361 375. Springer, 2007.