Nina Narodytska
email: nina.n@samsung.com

Thierry Petit
email: tpetit@wpi.edu

Mohamed Siala
email: mohamed.siala@insight-centre.org

Toby Walsh
email: toby.walsh@nicta.com.au

Three Generalizations of the FOCUS Constraint

s i,j = [i, i + 1, . . . , j], 0 ≤ i ≤ j < n. For each variable x, we denote by D(x) the domain of x and finally, we let |E| be the size of a collection E. Definition 1 ( [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]) Let y c be a variable. Let k and len be two integers, 1 ≤ len ≤ |X|. An instantiation of X ∪ {y c } satisfies FOCUS(X, y c , len, k ) iff there exists a set S X of disjoint sequences of indices s i,j such that three conditions are all satisfied:

1. |S X | ≤ y c 2. ∀x l ∈ X, x l > k ⇔ ∃s i,j ∈ S X such that l ∈ s i,j 3. ∀s i,j ∈ S X , j -i + 1 ≤ len Example 1 Let k = 0, D(y c ) = {2}, X = [x 0 , .., x 5 ], D(x 0 ) = {1}, D(x 1 ) = {3}, D(x 2 ) = {1}, D(x 3 ) = {0}, D(x 4 ) = {1}, D(x 5 ) = {0}. If len = 6, then FOCUS(X, y c , len, k ) is satisfied since we can have 2 disjoint sequences of length ≤ 6 of consecutive variables with a value strictly positive, i.e., x 0 , x 1 , x 2 , and x 4 . If len = 2, FOCUS(X, y c , len, k ) becomes violated since it is impossible to include all the strictly positive variables in X with only 2 sequences of length ≤ 2.

FOCUS can be used in various contexts including cumulative scheduling problems where some excesses of capacity can be tolerated to obtain a solution [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]. In a cumulative scheduling problem, we are scheduling activities, and each activity consumes a certain amount of some resource. The total quantity of the resource available is limited by a capacity. Excesses can be represented by variables [START_REF] De Clercq | Filtering algorithms for discrete cumulative problems with overloads of resource[END_REF]. In practice, excesses might be tolerated by, for example, renting a new machine to produce more resource. Suppose the rental price decreases proportionally to its duration: it is cheaper to rent a machine during a single interval than to make several rentals. On the other hand, rental intervals have generally a maximum possible duration. FOCUS can be set to concentrate (non null) excesses in a small number of intervals, each of length at most len.

Unfortunately, the usefulness of FOCUS is hindered by the rigidity of its semantics. For example, we might be able to rent a machine from Monday to Sunday but not use it on Friday. It is a pity to miss such a solution with a smaller number of rental intervals because FOCUS imposes that all the variables within each rental interval take a high value. Moreover, a solution with one rental interval of two days is better than a solution with a rental interval of four days. Unfortunately, FOCUS only considers the number of disjoint sequences, and does not consider their length.

Consider a simple example of a resource R with a capacity equal to 3. We use a sequence of variables [x 0 , .., x 9 ] to model the amount of consumed capacity at time unit i (e.g., one day). Suppose that some activities are already scheduled on R such that the current assignment of [x 0 , .., x 9 ] is:

[x 0 , .., x 9 ]: 4 2 4 2 2 0 0 0 0 0

In this example, the first day requires a capacity equal to 4, the second requires 2, etc. The standard capacity constraints are exceeded in x 0 and x 2 .

Suppose that an additional activity has to be scheduled on this resource. The new activity has a duration of 5 days, each of which consumes 2 units of capacity. The followings sequence (denoted S 1 ) shows the new resource consumption if we start the new activity at x 1 .The red values show the new capacity requirement after adding the new activity.

[x 0 , .., x 9 ] 4 4 6 4 4 2 0 0 0 0

The new sequence S 1 satisfies FOCUS(X, [START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF][START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF], 5, 3) since we have only one subsequence where the capacity constraints are all exceeded (i.e. x 0 , x 1 , x 2 , x 3 , x 4 ). However, there is no possible way to satisfy the constraint if the length is equal to 3. FOCUS(X, [START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF][START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF], 3, 3) is violated. Consider now a form of relaxation by allowing some variables in the sub-sequences to have values that do not exceed capacity. In this case, a solution is possible if we start the additional activity at x 5 (denoted S 2 ). That is:

[x 0 , .., x 9 ]: 4 2 4 2 2 2 2 2 2 2

The unique subsequence in S 2 where some capacity constraints are exceeded is x 0 , x 1 , x 2 . Relaxing FOCUS in this sense might be very useful in practice. Consider now again FOCUS(X, [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF][START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF], 5, 3). The two solutions S 1 and S 2 satisfy the constraint. Notice that there is 6 capacity excesses in S 1 (i.e., in x 0 , x 1 , x 2 , x 3 , x 4 ) and only 2 in S 2 (i.e., in x 0 and x 2 ). Therefore, one might prefer S 2 since we have less capacity excesses although the project ends later. Restricting the length subsequences to be at most 2 in this example will prune the first solution.

We tackle those issues in this paper by means of three generalizations of FOCUS. SPRINGYFOCUS tolerates within each sequence s i,j ∈ S X some values v ≤ k . To keep the semantics of grouping high values, their number is limited in each s i,j by an integer argument. WEIGHTEDFOCUS adds a variable to count the length of sequences, equal to the number of variables taking a value v > k . The most generic one, WEIGHTEDSPRINGYFOCUS, combines the semantics of SPRINGYFOCUS and WEIGHTEDFOCUS. Propagating such constraints, i.e. complementary to an objective function, is well-known to be important [START_REF] Petit | Global propagation of practicability constraints[END_REF][START_REF] Schaus | Scalable load balancing in nurse to patient assignment problems[END_REF]. We present and experiment with filtering algorithms and decompositions therefore for each constraint. One of the decompositions highlights a relation between SPRINGYFOCUS and a tractable Integer Linear Programming (ILP) problem.

The rest of this paper is organized as follows : We give in Section 2 a short background on Constraint Programming and Network Flows. Next, in Sections 3, 4 and 5, we present three generations of the FOCUS constraint (denoted by SPRINGYFOCUS, WEIGHTEDFOCUS, and WEIGHTEDSPRINGYFOCUS respectively). In particular, we provide complete filtering algorithms as well as ILP formulations and CSP decompositions. Finally, we evaluate, in Section 6, the impact of the new filtering compared to decompositions.

Background

A constraint satisfaction problem (CSP) is defined by a set of variables, each with a finite domain of values, and a set of constraints specifying allowed combinations of values for subsets of variables. For each variable x, we denote by min(x) (respectively max(x)) the minimum (respectively maximum) value in D(x). Given a constraint C, we denote by Scope(C) the set of variables constrained by C. A solution is an assignment of values to the variables satisfying the constraints.

Constraint solvers typically explore partial assignments enforcing a local consistency property using either specialized or general purpose filtering algorithms [START_REF] Rossi | Walsh Handbook of Constraint Programming[END_REF]. A filtering algorithm (called also a propagator) is usually associated with one constraint, to remove values that cannot belong to an assignment satisfying this constraint. A local consistency formally characterizes the impact of filtering algorithms. The two most used local consistencies are domain consistency (DC) and bound consistency (BC). A support for a constraint C is a tuple that assigns a value to each variable in Scope(C) from its domain which satisfies C. A bounds support for a constraint C is a tuple that assigns a value to each variable in Scope(C) which is between the maximum and minimum in its domain which satisfies C. A constraint C is domain consistent (DC) if and only if for each variable x i ∈Scope(C), every value in the current domain of x i belongs to a support. A constraint C is bounds consistent (BC) if and only if for each variable x i ∈Scope(C), there is a bounds support for the maximum and minimum value in its current domain. A CSP is DC/BC if and only if each constraint is DC/BC. Regarding FOCUS, a complete filtering algorithm (i.e. achieving domain consistency) is proposed in [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF] running in O(n) time complexity.

A flow network is a weighted directed graph G = (V, E) where each edge e has a capacity between non-negative integers l(e) and u(e), and an integer cost w(e). A feasible flow in a flow network between a source (s) and a sink (t), (s, t)-flow, is a function f : E → Z + satisfying two conditions: f (e) ∈ [l(e), u(e)], ∀e ∈ E and the flow conservation law that ensures that the amount of incoming flow should be equal to the amount of outgoing flow for all nodes except the source and the sink. The value of a (s, t)-flow is the amount of flow leaving the sink s. The cost of a flow f is w(f ) = e∈E w(e)f (e). A minimum cost flow is a feasible flow with the minimum cost [START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF].

Springy FOCUS

Definition

In Definition 1, each sequence in S X contains exclusively values v > k. In many practical cases, this property is too strong.

Consider one simple instance of the problem in the introduction (depicted in Figure 1) for a given resource of capacity 3. Each variable x i ∈ X represents the resource consumption and is defined per unit of time (e.g., one day). Initially, 4 activities are fixed (drawing A) as follows:

1. Activity 1 starts at day 0 and requires 4 units of capacity during one day 2. Activity 2 starts at day 1 and requires 2 units of capacity during one day 3. Activity 3 starts at day 2 and requires 4 units of capacity during one day 4. Activity 4 starts at day 3 and requires 2 units of capacity during two days Suppose now that an additional activity with 2 units of capacity and a duration of 5 days remains to be scheduled. Suppose also that the domain of the starting time of the new activity is D(st) = [START_REF] Ahuja | Orlin Network Flows: Theory, Algorithms, and Applications[END_REF][START_REF] Demassey | A cost-regular based hybrid column generation approach[END_REF]. If FOCUS(X, y c = 1, 5, 3) is imposed then this activity must start at day 1 (solution B). We have one 5 day rental interval. Assume now that the new machine may not be used every day. Solution (C) gives one rental of 3 days instead of 5. Furthermore, if len = 4 the problem will have no solution using FOCUS, while this latter solution still exists in practice. This is paradoxical, as relaxing the condition that sequences in the set S X of Definition 1 take only values v > k deteriorates the concentration power of the constraint. Therefore, we propose a soft relaxation of FOCUS, where at most h values less than k are tolerated within each sequence in S X .

Definition 2 Let y c be a variable and k , len, h be three integers, 1 ≤ len ≤ |X|, 0 ≤ h < len -1. An instantiation of X ∪ {y c } satisfies SPRINGYFOCUS(X, y c , len, h, k ) iff there exists a set S X of disjoint sequences of indices s i,j such that four conditions are all satisfied:

1. |S X | ≤ y c 2. ∀x l ∈ X, x l > k ⇒ ∃s i,j ∈ S X such that l ∈ s i,j 3. ∀s i,j ∈ S X , j -i + 1 ≤ len, x i > k and x j > k. 4. ∀s i,j ∈ S X , |{l ∈ s i,j , x l ≤ k }| ≤ h

Filtering Algorithm

Bounds consistency (BC) on SPRINGYFOCUS is equivalent to domain consistency: any solution can be turned into a solution that only uses the lower bound min(x l ) or the upper bound max(x l ) of the domain D(x l ) of each x l ∈ X (this observation was made for FOCUS [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]). Thus, we propose a BC algorithm. The first step is to traverse X from x 0 to x n-1 , to compute the minimum possible number of disjoint sequences in S X (a lower bound for y c ), the focus cardinality, denoted fc(X). We give a formal definition.

Definition 3 Focus cardinality

Let X be a sequence of variables subject to SPRINGYFOCUS(X, y c , len, h, k ). The focus cardinality of any subsequence s ⊂ X, denoted fc(s), is defined as follows:

fc(s) = min ω∈D(yc ) {SPRINGYFOCUS(s, y c ω , len, h, k ) is satisfiable | D(y c ω ) = {ω}}
Definition 4 Given x l ∈ X, we consider three quantities.

1. p(x l , v ≤ ) is the focus cardinality of [x 0 , x 1 , . . . , x l ], assuming x l ≤ k , and

∀s i,j ∈ S [x0,x1,...,x l ] , j = l. 2. p S (x l , v ≤ ), 0 < l < n -1, is the focus cardinality of [x 0 , x 1 , . . . , x j ], where l < j < n, assuming x l ≤ k and ∃i, 0 ≤ i < l, s i,j ∈ S [x0,x1,...,xj ] . p S (x 0 , v ≤ ) = p S (x n-1 , v ≤ ) = n + 1. 3. p(x l , v > ) is the focus cardinality of [x 0 , x 1 , . . . , x l ] assuming x l > k .
Any quantity is equal to n + 1 if the domain D(x l ) of x l makes impossible the considered assumption.

We shall use the above notations throughout the paper.

Property 1 fc(X) = min(p(x n-1 , v ≤ ), p(x n-1 , v > )).
Proof By construction from Definitions 2 and 4.

To compute the quantities of Definition 4 for x l ∈ X we use two additional measures. Proofs of following recursive Lemmas 1 to 4 omit the obvious cases where quantities take the default value n + 1.

Definition 5 plen(x l ) is the minimum length of a sequence in S [x0,x1,...,x l ] contain- ing x l among instantiations of [x 0 , x 1 , . . . , x l ] where the number of sequences is fc([x 0 , x 1 , . . . , x l ]). plen(x l )=0 if ∀s i,j ∈ S [x0,x1,...,x l ] , j = l.
Lemma 1 (initialization) p(x 0 , v ≤ ) = 0 if min(x 0 ) ≤ k, and n + 1 otherwise; p S (x 0 , v ≤ ) = n + 1; p(x 0 , v > ) = 1 if max(x 0 ) > k and n + 1 otherwise; plen(x 0 ) = 1 if max(x 0 ) > k and 0 otherwise; card (x 0 ) = 0.
Proof From item 4 of Definition 2, a sequence in S X cannot start with a value v ≤ k. Thus, p S (x 0 , v ≤ ) = n + 1 and card (x 0 ) = 0. If x 0 can take a value v > k then by Definition 4, p(x 0 , v > ) = 1 and plen(x 0 ) = 1.

We now consider a variable x l ∈ X, 0 < l < n.

Lemma 2 (p(x l , v ≤ )) If min(x l ) ≤ k then p(x l , v ≤ ) = min(p(x l-1 , v ≤ ), p(x l-1 , v > )), else p(x l , v ≤ ) = n + 1.
Proof If min(x l ) ≤ k then p S (x l-1 , v ≤ ) must not be considered: it would imply that a sequence in S X ends by a value v ≤ k for x l-1 . From Property 1, the focus cardinality of the previous sequence is min

(p(x l-1 , v ≤ ), p(x l-1 , v > )). Lemma 3 (p S (x l , v ≤ )) If min(x i ) > k, p S (x i , v ≤ ) = n + 1. Otherwise, if plen(x i-1 ) ∈ {0, len -1, len} ∨ card (x i-1 ) = h then p S (x i , v ≤ ) = n + 1, else p S (x i , v ≤ ) = min(p S (x i-1 , v ≤ ), p(x i-1 , v > )).
Proof If min(x i ) ≤ k we have three cases to consider. (1) If either plen(x i-1 ) = 0 or plen(x i-1 ) = len then from item 3 of Definition 2 a sequence in S X cannot start with a value v i ≤ k: p S (x i , v ≤ ) = n + 1. (2) If plen(x i-1 ) = len -1 then from Definition 2 the current variable x i cannot end the sequence with a value

v i ≤ k. (3) Otherwise, from item 3 of Definition 2, p(x i-1 , v ≤ ) is not considered. Thus, from Property 1, p S (x i , v ≤ ) = min(p S (x i-1 , v ≤ ), p(x i-1 , v > )). Lemma 4 (p(x l , v > )) If max(x l ) ≤ k then p(x l , v > )=n + 1. Otherwise, If plen(x l-1 ) ∈ {0, len}, p(x l , v > ) = min(p(x l-1 , v > )+1, p(x l-1 , v ≤ )+ 1), else p(x l , v > ) = min(p(x l-1 , v > ), p S (x l-1 , v ≤ ), p(x l-1 , v ≤ ) + 1).
Proof If plen(x l-1 ) ∈ {0, len} a new sequence has to be considered: p S (x l-1 , v ≤ ) must not be considered, from item 3 of Definition 2. Thus, p(x l , v > ) = min(p(x l-1 , v > ) + 1, p(x l-1 , v ≤ ) + 1). Otherwise, either a new sequence has to be considered (p(x l-1 , v ≤ ) + 1) or the value is equal to the focus cardinality of the previous sequence ending in x l-1 .

Proposition 1 (plen(x l )) If min (p S (x l-1 , v ≤ ), p(x l-1 , v > )) < p(x l-1 , v ≤ ) + 1 ∧ plen (x l-1 ) < len then plen(x l ) = plen(x l-1 ) + 1. Otherwise, if p(x l , v > )) < n + 1 then plen(x l ) = 1, else plen(x l ) = 0.
Proof By construction from Definition 5 and Lemmas 1, 2, 3 and 4.

Proposition 2 (card (x l )) If plen(x l ) = 1 then card (x l ) = 0. Otherwise, if p(x l , v > ) = n + 1 then card (x l ) = card (x l-1 ) + 1, else card (x l ) = card (x l-1 ).

Proof By construction from Definition 5, 6 and Lemmas 1 and 4.

Algorithm 1 implements the lemmas with pre

[l][0][0] = p(x l , v ≤ ), pre[l][0][1] = p S (x l , v ≤ ), pre[l][1] = p(x l , v > ), pre[l][2] = plen(x l ), pre[l][3] = card (x l ).
The principle of Algorithm 2 is the following. First, lb = f c(X) is computed with x n-1 . We execute Algorithm 1 from x 0 to x n-1 and conversely (arrays pre and suf ). We thus have for each quantity two values for each variable x l . To aggregate them, we implement regret mechanisms directly derived from Propositions 1 and 2, according to the parameters len and h. Line 4 is optional but it avoids some work when the variable y c is fixed, thanks to the same property as FOCUS (see [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]). Algorithm 2 performs a constant number of traversals of the set X. Its time complexity is O(n), which is optimal.

Algorithm 1: MINCARDS(X, len, k , h): Integer matrix

pre := new Integer[|X|][4][] ; for l ∈ 0..n -1 do pre[l][0] := new Integer[2]; / * Initialization from Lemma 1 * / if min(x 0 ) ≤ k then pre[0][0][0] := 0 ; else pre[0][0][0] := n + 1 ; pre[0][0][1] := n + 1 ; if max(x 0 ) > k then pre[0][1] := 1 ; else pre[0][1] := n + 1 ; if max(x 0 ) > k then pre[0][2] := 1 ; else pre[0][2] := 0 ; pre[0][3] := 0 ; for l ∈ 1..n -1 do / * Lemma 2 * / if min(x l ) ≤ k then pre[l][0][0] := min(pre[l -1][0][0], pre[l -1][1]) ; else pre[l][0][0] := n + 1 ; / * Lemma 3 * / if min(x l ) > k then pre[l][0][1] := n + 1 ; else if pre[l -1][2] ∈ {0, len -1, len} ∨ pre[l -1][3] = h then 27 pre[l][0][1] := n + 1 ; else 29 pre[l][0][1] := min(pre[l -1][0][1], pre[i -1][0][0]) ; / * Lemma 4 * / if max(x l ) ≤ k then pre[l][1] := n + 1 ; else if pre[l -1][2] ∈ {0, len} then 34 pre[l][1] = min(pre[l -1][1] + 1, pre[l -1][0][0] + 1) ; else 36 pre[l][1] = min(pre[l -1][1], pre[l -1][0][1], pre[l -1][0][0] + 1) / * Proposition 1 * / if min (pre[l -1][0][1], pre[l -1][1]) < pre[l -1][0][0] + 1 ∧ pre[l -1][2] < len then pre[l][2] = pre[l -1][2] + 1 ; else if pre[l][1] < n + 1 then 41 pre[l][2] := 1 ; else 43 pre[l][2] := 0 ; / * Proposition 2 * / if pre[l][2] = 1 then pre[l][3] := 0 ; else if pre[l][1] = n + 1 then 48 pre[l][3]) := pre[l -1] + 1; else 50 pre[l][3]) := pre[l -
if pre[l][0][0] + suf [n -1 -l][0][0] > max(yc) then 8
Integer regret := 0; Integer add := 0;

9 if pre[l][1] ≤ pre[l][0][1] then add := add + 1 ; 10 if suf [n -1 -l][1] ≤ suf [n -1 -l][0][1] then add:=add+1 ; 11 if pre[l][2] + suf [n -1 -l][2] -1 ≤ len ∧ pre[l][3] + suf [n -1 -l][3] + add -1 ≤ h then regret := 1 ; 12 if pre[l][0][1] + suf [n -1 -l][0][1] -regret > max(yc) then D(x i ) := D(x i )\ [min(x i ), k] ; 13
Integer regret := 0;

14 if pre[l][2] + suf [n -1 -l][2] -1 ≤ len ∧ pre[l][3] + suf [n -1 -l][3] -1 ≤ h then regret := 1 ; 15 if pre[l][1] + suf [n -1 -l][1] -regret > max(yc) then 16 D(x i ) := D(x i )\ ]k, max(x i )];
17 return X ∪ {yc};

Integer Linear Programming formulation

In this section we present a new Integer Linear Programming (ILP) formulation of SPRINGYFOCUS. This connection highlights a relation between SPRINGYFOCUS and a tractable ILP problem. It adds one more constraint to a bag of constraints that can be propagated using shortest path or network flow reformulations [START_REF] Régin | A filtering algorithm for constraints of difference in CSPs[END_REF][START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF][START_REF] Maher | Flow-based propagators for the sequence and related global constraints[END_REF]. We first present a bounds disentailment technique. We use the following notations from [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]. Definition 7 ( [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]) Given an integer k , a variable x l ∈ X is:

-Penalizing, (P k ), iff min(x l ) > k.

-Neutral, (N k ), iff max(x l ) ≤ k.

-Undetermined, (U k ), otherwise.

We say x l ∈ P k iff x l is labelled P k , and similarly for U k and N k .

The main observation behind the reformulation is that we can relax the requirement of disjointness of sequences in S X (Definition 2) and find a solution of the SPRINGYFOCUS constraint. This solution can be transformed into a solution where sequences in S X are disjoint as we can truncate the overlaps. If we drop the requirement of disjointness of sequences in S X then we only need to consider at most n possible sequences s i,i+leni-1 , i ∈ {0, 1, . . . , n -1}, x i and x i+leni-1 are not neutral, and len i is the maximal possible length of a sequence that starts at the ith position. Note that len i does not have to be equal to len as s i,i+leni-1 can cover at most h variables that take values less than or equal to k. We call the set of these sequences S o X . We denote the SPRINGYFOCUS constraint without the disjointness requirement SPRINGYFOCUSOVERLAP. More formally we define SPRINGYFOCUSOVERLAP as follows.

Definition 8 Let y c be a variable and k , len, h be three integers, 1 ≤ len ≤ |X|, 0 ≤ h < len -1. An instantiation of X ∪ {y c } satisfies SPRINGYFOCUSOVERLAP(X, y c , len, h, k ) iff there exists a set S X ⊆ S o X of sequences (not necessary disjoint) of indices s i,j such that four conditions are all satisfied:

1. |S X | ≤ y c 2. ∀x l ∈ X, x l > k ⇒ ∃s i,j ∈ S X such that l ∈ s i,j 3. ∀s i,j ∈ S X , j -i + 1 ≤ len, x i > k and x j > k 4. ∀s i,j ∈ S X , |{l ∈ s i,j , x l ≤ k }| ≤ h Lemma 5 SPRINGYFOCUS(X, y c , len, h, k ) has a solution iff SPRINGYFOCUSOVERLAP(X, y c , len, h, k ) has a solution.
Proof ⇐ Let I[X ∪ {y c }] be a solution of SPRINGYFOCUSOVERLAP. We order sequences in S X by their starting points and process them in this order. Let s i,i+leni-1 and s j,j+lenj -1 be the first two consecutive sequences in S X that overlap. We update S X . First, we remove s j,j+lenj -1 : S X = S X \ {s j,j+lenj -1 }. Consider a sequence s i+leni,j+lenj -1 . By definition, x j+lenj -1 > k . If s i+leni,j+lenj -1 has a prefix that contains only neutral variables then we cut it from the sequence and obtain s i ,j+lenj -1 . We add this sequence to our set: S X = S X ∪{s i ,j+lenj -1 }. So, we cut the prefix of s j,j+lenj -1 to avoid the overlap and made sure that the new sequence does not start or end at a neutral variable. This does not change the cardinality |S X |. We continue this procedure for the rest of the sequences. The updated set S X covers the same set of penalizing variables as the original set and all sequences are disjoint.

⇒ Let I[X ∪{y c }] be a solution of SPRINGYFOCUS. We extend each sequence to its maximal length to the right. This gives a solution of SPRINGYFOCUSOVERLAP.

Example 3 Consider SPRINGYFOCUSOVERLAP from Example 2. S X = {s 0,2 , s 5,7 , s 7,8 } is a possible solution (dashed lines in Figure 2(a)). We can cut the prefix of s 7,8 to avoid an overlap between s 5,7 and s 7,8 . We obtain s 8,8 which does not start or finish at a neutral variable. Hence, S X = (S X ∪ {s 8,8 }) \ {s 7,8 } = {s 0,2 , s 5,7 , s 8,8 }.

Thanks to Lemma 5 we build an ILP reformulation for SPRINGYFOCUSOVERLAP, solve this ILP and transform to a solution of the SPRINGYFOCUS constraint. We introduce one Boolean variable sv i for each sequence in S o X . We can write an integer linear program:

Minimize i:s i,i+len i ∈S o X sv i (1) {svi:xj ∈s i,i+len i -1 } sv i ≥ 1 ∀x j ∈ P k (2)
sv i ∈ {0, 1} ∀sv i . (3)
Lemma 6 SPRINGYFOCUSOVERLAP(X, y c , len, h, k ) is satisfiable iff the ILP system 1-3 has a solution of cost less than or equal to max(y c ).

Proof ⇐ Suppose the system described by Equations 1-3 has a solution I[sv]. We define S = {s i,i+leni |sv i = 1}. Equation 2 ensures that at least one sequence covers a penalizing variable. Equation 1 ensures that the number of selected sequences is at most max(y c ).

As the rest of uncovered variables in X are undetermined or neutral variables, we can construct an assignment based on S X . We set all undetermined variables covered by S X to 1 and all undetermined variables uncovered by S X to 0. This assignment clearly satisfies SPRINGYFOCUSOVERLAP(X, y c , len, h, k ).

⇒ Suppose there is a solution of the SPRINGYFOCUSOVERLAP(X, y c , len, h, k ) constraint I[X ∪ {y c }] and S X = {s i1,j1 , . . . , s ip,jp } be the set of corresponding sequences. We set variable sv i to 1 iff s i,i+leni-1 ∈ S X . This assignment satisfies Equations 1-3.

Next we note that the ILP system 1-3 has the consecutive ones properties on columns. This means that the corresponding matrix can be transformed to a network flow matrix using a procedure described by Veinott and Wagner [START_REF] Wagner | Optimal capacity scheduling I[END_REF]. We consider the transformation on SPRINGYFOCUS from Example 5. This transformation is similar to the one used to propagate the SEQUENCE constraint [START_REF] Maher | Flow-based propagators for the sequence and related global constraints[END_REF].

Example 4 Consider SPRINGYFOCUS from Example 2. We build an ILP that corresponds to an equivalent SPRINGYFOCUSOVERLAP constraint using Equations 1-3. Note that we do not introduce variables sv 1 , sv 2 , sv 3 and sv 4 for discarded sequences s 1,3 , s 2,3 , s 3,3 and s 4,6 :

Minimize i∈{0,5,6,7,8} sv i ( 4
)
sv 0 ≥ 1 (5) sv 5 ≥ 1 (6) sv 5 + sv 6 + sv 7 ≥ 1, (7)
sv 6 + sv 7 + sv 8 ≥ 1, (8)
where sv i ∈ {0, 1}. By introducing surplus/slack variables, z i , we convert this to a set of equalities:

Minimize i∈{0,5,6,7,8} sv i (9) sv 0 -z 0 = 1 (10) sv 5 -z 1 = 1 (11) sv 5 + sv 6 + sv 7 -z 2 = 1, (12)
sv 6 + sv 7 + sv 8 -z 3 = 1, (13)
In matrix form, this is:

    1 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 -1 0 0 0 1 1 1 0 0 0 -1 0 0 0 1 1 1 0 0 0 -1               sv 0 . . . sv 8 z 0 . . . z 3           =    1 . . . 1   
We append a row of zeros to the matrix and subtract the ith row from i + 1th row for i = 1 to 4. These operations do not change the set of solutions. This gives:

      1 0 0 0 0 -1 0 0 0 -1 1 0 0 0 1 -1 0 0 0 0 1 1 0 0 1 -1 0 0 -1 0 0 1 0 0 1 -1 0 0 -1 -1 -1 0 0 0 1                 sv 0 . . . sv 8 z 0 . . . z 3           =         1 0 0 0 0 -1        
The corresponding network flow graph is shown in Figure 2(b). The dashed arcs have cost zero and solid arcs have cost one. Capacities are shown on arcs. We number nodes from 0 to 4 as we have 4 equations in the transformed ILP. We highlighted in grey a possible solution of cost 3. This solution corresponds to the solution from Example 3.

As the right hand side (RHS) of the ILP system 1-2 is a unit vector, the RHS in the transformed ILP is a vector (1, 0, . . . , 0, -1). In other words, we need to consume one unit of flow that enters the first node in the graph and leaves the last node in the graph. Hence, the problem of finding a min cost flow is equivalent to the problem of finding a shortest path in this graph from 0th to mth node, where m is the number of equations in ILP. Moreover, a shortest path can be found in linear time.

Lemma 7 Let G be a directed graph that corresponds to the SPRINGYFOCUS(X, y c , len, h, k ). A shortest path from 0th to mth node can be found in O(n) time.

Proof We show that there exists a shortest path from 0th to mth node that does not contain arcs (i + 1, i), i ∈ {0, 1, . . . , m -1}. We call these arcs backward arcs and call the remaining arcs -forward arcs.

First, we observe that each node in G has an outgoing arc, because the ith node, i ∈ {0, . . . , m -1} corresponds to the ith penalizing variable in the constraint and a sequence that starts at a penalizing variable is in S o X . Let π be a shortest path from 0 to m node that uses a backward arc. Consider the first occurrence of a sequence of backward arcs in π: π = (0, . . . , j, i , . . . , i, g, f, . . . , m), where i , . . . , i is a path using only backward arcs. As (i, g) is present in G then (i , g ), g ≤ g is present in G. Hence, we can modify the path π to π = (0, . . . , j, i , g , π , f, . . . , m), where (g , π , f ) is a path that uses backward arcs to reach f from g if (g , f ) / ∈ G. As the weight π is 0, the weight of the updated path π is the same as the weight of the original path. Then we apply the same argument to g and so on.

Hence, we can use a simple greedy algorithm to find the shortest path. We start at the 0th node and select the longest outgoing arc (0, i). In the node i, we again select the longest arc until will reach the mth node. As we know that there exists a shortest path that only uses forward arcs the greedy algorithm is optimal.

The same ILP reformulation can be done for the FOCUS constraint [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF], which is a special case of SPRINGYFOCUS. For these two constraints, we can use such a bounds disentailment procedure to obtain a O(n 2 ) filtering algorithm by successively applying the program to the two bounds of the domain of each variable in X.

Weighted FOCUS

We present WEIGHTEDFOCUS, that extends FOCUS with a variable z c limiting the the sum of lengths of all the sequences in S X , i.e., the number of variables covered by a sequence in S X . WEIGHTEDFOCUS distinguishes between solutions that are equivalent with respect to the number of sequences in S X but not with respect to their length, as Figure 3 shows. Definition 9 Let y c and z c be two integer variables and k , len be two integers, such that 1 ≤ len ≤ |X|. An instantiation of X ∪ {y c } ∪ {z c } satisfies WEIGHTEDFOCUS(X, y c , len, k , z c ) iff there exists a set S X of disjoint sequences of indices s i,j such that four conditions are all satisfied:

Definition

1. |S X | ≤ y c 2. ∀x l ∈ X, x l > k ⇔ ∃s i,j ∈ S X such that l ∈ s i,j 3. ∀s i,j ∈ S X , j -i + 1 ≤ len 4. si,j ∈S X |s i,j | ≤ z c .
It should be noted that there are some similarities between WEIGHTEDFOCUS and STRETCH [START_REF] Pesant | A Filtering Algorithm for the Stretch Constraint[END_REF]. Indeed given a sequence of variables, the STRETCH constraint restricts the occurrences of consecutive identical values. The particular case of WEIGHTEDFOCUS with Boolean variables is similar to a very specific case of STRETCH with Boolean variables, where only the occurrences of consecutive 1s is bounded. However, STRETCH does not restrict the number of such subsequences. Even though, the semantics behind STRETCH is quite different as the limitation of consecutive values is usually for many values along with many patterns whereas in WEIGHTEDFOCUS the restriction in only for values greater than a threshold. One limitation of WEIGHTEDFOCUS compared to STRETCH is that we do not restrict the minimum size of subsequences with excess. Another limitation is the nonpenalization of the extra resource consumption at each unit of time. That is, if k = 2, then excess of type x = 10 might be very costly compared to two excess of the type x = 5.

Filtering Algorithm

Dynamic Programming (DP) Principle Given a partial instantiation I X of X and a set of sequences S X that covers all penalizing variables in I X , we consider two terms: the number of variables in P k and the number of undetermined variables, in U k , covered by S X . We want to find a set S X that minimizes the second term. Given a sequence of variables s i,j , the cost cst(s i,j ) is defined as

cst(s i,j ) = |{p|x p ∈ U k , x p ∈ s i,j }|. We denote cost of S X , cst(S X ), the sum cst(S X ) = si,j ∈S X cst(s i,j ). Given I X we consider |P k | = |{x i ∈ P k }|. We have: si,j ∈S |s i,j | = si,j ∈S cst(s i,j ) + |P k |.
We start with explaining the main difficulty in building a propagator for WEIGHTEDFOCUS. The constraint has two optimization variables in its scope (i.e. y c and z c ) and we might not have a solution that optimizes both variables simultaneously. [START_REF][END_REF][START_REF] Maher | Flow-based propagators for the sequence and related global constraints[END_REF]), solution S X = {s 0,2 , s 3,5 }, z c = 6, minimizes y c = 2, while solution S X = {s 0,1 , s 2,3 , s 5,5 },

Example 5 Consider the set

X = [x 0 , x 1 , . . . , x 5 ] with domains [1, {0, 1}, 1, 1, {0, 1}, 1] and WEIGHTEDFOCUS(X, [2, 3], 3, 0,
y c = 3, minimizes z c = 4.
Example 5 suggests that we need to fix one of the two optimization variables and only optimize the other one. Our algorithm is based on a dynamic program [START_REF] Dasgupta | Algorithms[END_REF]. For each prefix of variables [x 0 , x 1 , . . . , x j ] and given a cost value c, it computes a cover of focus cardinality, denoted S c,j , which covers all penalized variables in [x 0 , x 1 , . . . , x j ] and has cost exactly c. If S c,j does not exist we assume that S c,j = ∞. S c,j is not unique as Example 6 demonstrates.

Example 6 Consider X = [x 0 , x 1 , . . . , x 7 ]
and WEIGHTEDFOCUS(X, [2, 2], 5, 0, [START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF][START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF]), with D(x i ) = {1}, i ∈ I, I = {0, 2, 3, 5, 7} and D(x i ) = {0, 1}, i ∈ {0, 1, . . . 7} \ I. Consider the subsequence of variables [x 0 , . . . , x 5 ] and S 1,5 . There are several sets of minimum cardinality that cover all penalized variables in the prefix [x 0 , . . . , x 5 ] and has cost 2, e.g. S 1 1,5 = {s 0,2 , s 3,5 } or S 2 1,5 = {s 0,4 , s 5,5 }. Assume we sort sequences by their starting points in each set. We note that the second set is better if we want to extend the last sequence in this set as the length of the last sequence s 5,5 is shorter compared to the length of the last sequence in S 1 1,5 , which is s 3,5 .

Example 6 suggests that we need to put additional conditions on S c,j to take into account that some sets are better than others. We can safely assume that none of the sequences in S c,j starts at undetermined variables as we can always set it to zero. Hence, we introduce a notion of an ordering between sets S c,j and define conditions that this set has to satisfy.

Ordering of sequences in S c,j . We introduce an order over sequences in S c,j . Given a set of sequences in S c,j , we sort them by their starting points. We denote last(S c,j ) the last sequence in S c,j in this order. If x j ∈ last(S c,j ) then |last(S c,j )| is, naturally, the length of last(S c,j ), otherwise |last(S c,j )| = ∞.

Ordering of sets S c,j , c ∈ [0, max(z c )], j ∈ {0, 1, . . . , n -1}. We define a comparison operation between two sets S c,j and S c ,j :

-S c,j < S c ,j iff |S c,j | < |S c ,j | or |S c,j | = |S c ,j | and |last(S c,j )| < |last(S c ,j )|. -S c,j = S c ,j iff |S c,j | = |S c ,j | and |last(S c,j )| = |last(S c ,j )|.
Note that we do not take account of cost in the comparison as the current definition is sufficient for us. Using this operation, we can compare all sets S c,j and S c,j of the same cost for a prefix [x 0 , . . . , x j ]. We say that S c,j is optimal iff satisfies the following 4 conditions. Proposition 3 (Conditions on S c,j )

1. S c,j covers all P k variables in [x 0 , x 1 , . . . , x j ], 2. cst(S c,j ) = c, 3. ∀s h,g ∈ S c,j , x h / ∈ U k , 4. S c,j
is the first set in the order among all sets that satisfy conditions 1-3.

As can be seen from definitions above, given a subsequence of variables x 0 , . . . , x j , S c,j is not unique and might not exist. However, if |S c,j | = |S c ,j |, c = c and j = j , then last(S c,j ) = last(S c ,j ).

Example 7 Consider WEIGHTEDFOCUS from Example 6. Consider the subsequence [x 0 , x 1 ]. S 0,1 = {s 0,0 }, S 1,1 = {s 0,1 }. Note that S 2,1 does not exist. Consider the subsequence [x 0 , . . . , x 5 ]. We have S 0,5 = {s 0,0 , s 2,3 , s 5,5 }, S 1,5 = {s 0,4 , s 5,5 } and S 2,5 = {s 0,3 , s 5,5 }. By definition, last(S 0,5 ) = s 5,5 , last(S 1,5 ) = s 5,5 and last(S 2,5 ) = s 5,5 . Consider the set S 1,5 . Note that there exists another set S 1,5 = {s 0,0 , s 2,5 } that satisfies conditions 1-3. Hence, it has the same cardinality as S 1,5 and the same cost. However, S 1,5 < S 1,5 as |last(S 1,5

)| = 1 < |last(S 1,5 )| = 3. Bounds disentailment Each cell in the dynamic programming table f c,j , c ∈ [0, z U c ], j ∈ {0, 1, . . . , n -1}, where z U c = max(z c ) -|P k |,
is a pair of values q c,j and l c,j , f c,j = {q c,j , l c,j }, stores information about S c,j . Namely, q c,j = |S c,j |, l c,j = |last(S c,j )| if last(S c,j ) = ∞ and ∞ otherwise. We say that f c,j /q c,j /l c,j is a dummy (takes a dummy value) iff f c,j = {∞, ∞}/q c,j = ∞/l c,j = ∞. If y 1 = ∞ and y 2 = ∞ then we assume that they are equal. We introduce a dummy variable x -1 , D(x -1 ) = {0} and a row f -1,j , j = -1, . . . , n -1 to keep uniform notations.

Algorithm 3: Weighted FOCUS(x 0 , . . . , x n-1 ) Algorithm 3 gives pseudocode for the propagator. The intuition behind the algorithm is as follows. We emphasize again that by cost we mean the number of covered variables in U k .

1 for c ∈ -1..z U c do 2 for j ∈ -1..n -1 do 3 f c,j ← {∞, ∞}; 4 f 0,-1 ← {0, 0} ; 5 for j ∈ 0..n -1 do 6 for c ∈ 0..j do 7 if x j ∈ P k then / * penalizing * / 8 if (l c,j-1 ∈ [1, len)) ∨ (q c,j-1 = ∞) then 9 f c,j ← {q c,j-1 , l c,j-1 + 1}; 10 else f c,j ← {q c,j-1 + 1, 1} ; 11 if x j ∈ U k then / * undetermined * / 12 if (l c-1,j-1 ∈ [1, len) ∧ q c-1,j-1 = q c,j-1 ) ∨ (q c,j-1 = ∞) then f c,j ← {q c-1,j-1 , l c-1,j-1 + 1} ;
If x j ∈ P k then we do not increase the cost of S c,j compared to S c,j-1 as the cost only depends on undetermined variables. Hence, the best move for us is to extend last(S c,j-1 ) or start a new sequence if it is possible. This is encoded in lines 9 and 10 of the algorithm. Figure 4(a) gives a schematic representation of these arguments.

If x j ∈ U k then we have two options. We can obtain S c,j from S c-1,j-1 by increasing cst(S c-1,j-1 ) by one. This means that x i will be covered by last(S c,j ). Alternatively, from S c,j-1 by interrupting last(S c,j-1 ). This is encoded in line 12 of the algorithm (Figure 4(b)).

If x j ∈ N k then we do not increase the cost of S c,j compared to S c,j-1 . Moreover, we must interrupt last(S c,j-1 ), line 15 (Figure 4(c), ignore the gray arc).

First we prove a property of the dynamic programming table. We define a comparison operation between f c,j and f c ,j induced by a comparison operation between S c,j and S c ,j :

f c,j < f c ,j if (q c,j < q c ,j ) or (q c,j = q c ,j and l c,j < l c ,j ).

f c,j = f c ,j if (q c,j = q c ,j and l c,j = l c ,j ).

In other words, as in a comparison operation between sets, we compare by the cardinality of sequences, |S c,j | and |S c ,j |, and, then by the length of the last sequence in each set, last(S c,j ) and last(S c ,j ).

First, we prove two technical results.

Lemma 8 Consider WEIGHTEDFOCUS([x 0 , . . . , x n-1 ], y c , len, k, z c ). Let f be dynamic programming table returned by Algorithm 3. Then the non-dummy values of f c,j are consecutive in each column, so that there do not exist c, c , c , 0 ≤ c < c < c ≤ z U c , such that f c ,j is dummy and f c,j , f c ,j are non-dummy.

Proof We prove by induction on the length of the sequence. The base case is trivial as

f 0,-1 = {0, 0} and f c,-1 = {∞, ∞}, c ∈ [-1] ∪ [1, z U c ].
Suppose the statement holds for j -1 variables.

Suppose there exist c, c , c , 0 ≤ c < c < c ≤ z U c , such that f c ,j is dummy and f c,j , f c ,j are non-dummy.

Case 1. Consider the case x j ∈ P k . By Algorithm 3, lines 9 and 10, q c,j ∈ [q c,j-1 , q c,j-1 + 1], q c ,j ∈ [q c ,j-1 , q c ,j-1 + 1] and q c ,j ∈ [q c ,j-1 , q c ,j-1 + 1]. As f c ,j is dummy and f c,j , f c ,j are non-dummy, f c ,j-1 must be dummy and f c,j-1 , f c ,j-1 must be non-dummy. This violates induction hypothesis.

Case 2. Consider the case x j ∈ U k . By Algorithm 3, line 12, q c,j = min(q c-1,j-1 , q c,j-1 ), q c ,j = min(q c -1,j-1 , q c ,j-1 ) and q c ,j = min(q c -1,j-1 , q c ,j-1 ). As f c ,j is dummy, then both f c -1,j-1 and f c ,j-1 must be dummy. As f c,j is non-dummy, then one of f c-1,j-1 and f c,j-1 is non-dummy. As f c ,j is non-dummy, then one of f c -1,j-1 and f c ,j-1 is non-dummy. We know that c -1 < c ≤ c -1 < c ≤ c -1 < c or c < c < c . This leads to violation of induction hypothesis.

Case 3. Consider the case x j ∈ N k . By Algorithm 3, line 15, q c,j = q c,j-1 , q c ,j = q c ,j-1 and q c ,j = q c ,j-1 . Hence, f c ,j-1 is dummy and f c,j-1 , f c ,j-1 are non-dummy. This leads to violation of induction hypothesis.

Proposition 4 Consider WEIGHTEDFOCUS([x 0 , . . . , x n-1 ], y c , len, k, z c ). Let f be dynamic programming table returned by Algorithm 3. The elements of the first row are non-dummy: f 0,j , j = -1, . . . , n are non-dummy.

Proof We prove by induction on the length of the sequence. The base case is trivial as f 0,-1 = {0, 0}. Suppose the statement holds for j -1 variables.

Case 1. Consider the case x j ∈ P k . As f 0,j-1 is non-dummy then by Algorithm 3, lines 9-10, f 0,j is non-dummy.

Case 2. Consider the case x j ∈ U k . Consider the condition (l -1,j-1 ∈ [1, len) ∧ q -1,j-1 = q 0,j-1 ) ∨ (q 0,j-1 = ∞) at line 12. By the induction hypothesis, q 0,j-1 = ∞. By the initialization procedure of the dummy row, q -1,j-1 = ∞. Hence, this condition does not hold and, by line 13, f 0,j is non-dummy.

Case 3. Consider the case x j ∈ N k . As f 0,j-1 is non-dummy then by Algorithm 3, line 15, f 0,j is non-dummy.

We can now prove an interesting monotonicity property of Algorithm 3.

Lemma 9 Consider WEIGHTEDFOCUS(X, y c , len, k , z c ). Let f be dynamic programming table returned by Algorithm 3. Non-dummy elements f c,j are monotonically non increasing in each column, so that

f c ,j ≤ f c,j , 0 ≤ c < c ≤ z U c , j = [0, . . . , n -1].
Proof By transitivity and consecutivity of non-dummy values (Lemma 8) and the result that all elements in the 0th row are non-dummy (Proposition 4), it is sufficient to consider the case c = c + 1.

We prove by induction on the length of the sequence. The base case is trivial as f 0,-1 = {0, 0} and f c,0 are dummy, c ∈ [0, z U c ]. Suppose the statement holds for j -1 variables.

Consider the variable x j . Suppose, by contradiction, that f c,j < f c+1,j . Then either q c,j < q c+1,j or q c,j = q c+1,j , l c,j < l c+1,j . By induction hypothesis, we know that f c,j-1 ≥ f c+1,j-1 , hence, either q c,j-1 > q c+1,j-1 or q c,j-1 = q c+1,j-1 , l c,j-1 ≥ l c+1,j-1 .

We consider three cases depending on whether x j is a penalizing variable, an undetermined variable or a neutral variable.

Case 1. Consider the case x j ∈ P k . If q c,j-1 = ∞ then q c+1,j-1 = ∞ by the induction hypothesis. Hence, by Algorithm 3, line 9, f c,j and f c+1,j are dummy and equal. Suppose q c,j-1 = ∞. Then we consider four cases based on relative values of q c,j , q c+1,j , l c,j , l c+1,j , j ∈ {j -1, j}.

-Case 1a. Suppose q c,j < q c+1,j and q c,j-1 > q c+1,j-1 . By Algorithm 3, lines 9 and 10, q c,j ≥ q c,j-1 and q c+1,j ≤ q c+1,j-1 + 1. Hence, q c,j < q c+1,j implies q c+1,j-1 < q c,j < q c+1,j-1 + 1. We derive a contradiction. -Case 1b. Suppose q c,j < q c+1,j and q c,j-1 = q c+1,j-1 , l c,j-1 ≥ l c+1,j-1 . By Algorithm 3, lines 9 and 10, q c,j ≥ q c,j-1 and q c+1,j ≤ q c+1,j-1 + 1. Hence, q c,j < q c+1,j implies q c+1,j-1 = q c,j-1 ≤ q c,j < q c+1,j ≤ q c+1,j-1 + 1.

Hence, q c+1,j-1 = q c,j-1 = q c,j and q c+1,j = q c+1,j-1 + 1. As q c,j-1 = q c,j then l c,j-1 ∈ [1, len) by Algorithm 3 line 9. As q c+1,j = q c+1,j-1 + 1 then l c+1,j-1 ∈ {len, ∞} by Algorithm 3 line 10. This leads to a contradiction as l c,j-1 ≥ l c+1,j-1 . -Case 1c. Suppose q c,j = q c+1,j , l c,j < l c+1,j and q c,j-1 > q c+1,j-1 . Symmetric to Case 1b. -Case 1d. Suppose q c,j = q c+1,j , l c,j < l c+1,j and q c,j-1 = q c+1,j-1 , l c,j-1 ≥ l c+1,j-1 . By Algorithm 3, lines 9 and 10, q c,j ≥ q c,j-1 and q c+1,j ≤ q c+1,j-1 +1. Hence, q c,j = q c+1,j implies q c+1,j-1 = q c,j-1 ≤ q c,j = q c+1,j ≤ q c+1,j-1 + 1. Therefore, either q c,j = q c,j-1 ∧ q c+1,j = q c+1,j-1 or q c,j = q c,j-1 + 1 ∧ q c+1,j = q c+1,j-1 + 1.

If q c,j = q c,j-1 and q c+1,j = q c+1,j-1 then l c,j-1 ∈ [1, len) and l c+1,j-1 ∈ [1, len) by Algorithm 3 line 9. Hence, l c,j = l c,j-1 +1 and l c+1,j = l c+1,j-1 +1.

As l c,j-1 ≥ l c+1,j-1 , then l c,j ≥ l c+1,j . This leads to a contradiction with the assumption l c,j < l c+1,j .

If q c,j = q c,j-1 + 1 ∧ q c+1,j = q c+1,j-1 + 1 then l c,j-1 ∈ {len, ∞} and l c+1,j-1 ∈ {len, ∞} by Algorithm 3 line 10. Hence, l c,j = 1 and l c+1,j = 1. This leads to a contradiction with the assumption l c,j < l c+1,j .

Case 2. Consider the case x j ∈ U k . If q c,j-1 = ∞ then q c+1,j-1 = ∞ by the induction hypothesis. Hence, by Algorithm 3, line 12, f c,j and f c+1,j are dummy and equal.

Suppose q c,j-1 = ∞. Then we consider four cases based on relative values of q c,j , q c+1,j , l c,j , l c+1,j , j ∈ {j -1, j}.

-Case 2a Suppose q c,j < q c+1,j and q c,j-1 > q c+1,j-1 . By Algorithm 3, line 12, we know that q c+1,j-1 ≤ q c+1,j ≤ q c,j-1 and q c,j-1 ≤ q c,j ≤ q c-1,j-1 . By induction hypothesis, q c+1,j-1 ≤ q c,j-1 ≤ q c-1,j-1 . Hence, if q c,j ≤ q c+1,j then q c,j-1 ≤ q c,j ≤ q c+1,j ≤ q c,j-1 . Therefore, if q c,j < q c+1,j then we derive a contradiction. -Case 2b. Identical to Case 2b. -Case 2c. Suppose q c,j = q c+1,j , l c,j > l c+1,j and q c,j-1 > q c+1,j-1 . As q c,j-1 = q c+1,j-1 then q c+1,j-1 = q c+1,j (line 12). We also know q c,j-1 ≤ q c,j ≤ q c+1,j ≤ q c,j-1 from Case 1a. Putting everything together, we get q c,j-1 ≤ q c,j ≤ q c+1,j-1 < q c,j-1 . This leads to a contradiction. -Case 2d. Suppose q c,j = q c+1,j , l c,j < l c+1,j and q c,j-1 = q c+1,j-1 , l c,j-1 ≥ l c+1,j-1 . As we know from Case 1a q c+1,j-1 ≤ q c+1,j ≤ q c,j-1 , q c,j-1 ≤ q c,j ≤ q c-1,j-1 and q c,j-1 ≤ q c,j ≤ q c+1,j ≤ q c,j-1 . Hence, q c+1,j-1 = q c+1,j = q c,j-1 = q c,j . Consider two subcases. Suppose q c,j-1 < q c-1,j-1 . Then l c,j = ∞ (line 13). Hence, our assumption l c,j < l c+1,j is false. Suppose q c,j-1 = q c-1,j-1 . If l c-1,j-1 = len then l c,j = ∞ (line 13). Hence, our assumption l c,j < l c+1,j is false. Therefore, l c-1,j-1 ∈ [1, len) and l c,j-1 = l c-1,j-1 + 1. By induction hypothesis as q c+1,j-1 = q c,j-

1 = q c-1,j-1 then l c+1,j-1 ≤ l c,j-1 ≤ l c-1,j-1 . Hence, l c,j-1 ∈ [1, l c-1,j-1 ] ⊆ [1, len).
Therefore, l c+1,j = l c,j-1 + 1 ≤ l c-1,j-1 + 1 = l c,j-1 . This contradicts our assumption l c,j < l c+1,j . Case 3. Consider the case x j ∈ N k . This case follows immediately from Algorithm 3, line 15, and the induction hypothesis.

Lemma 10 Consider WEIGHTEDFOCUS(X, y c , len, k , z c ). The dynamic programming table f c,j = {q c,j , l c,j } c ∈ [0, z U c ], j = 0, . . . , n-1, is correct in the sense that if f c,j exists and it is non-dummy then a corresponding set of sequences S c,j exists and satisfies conditions 1-4. The time complexity of Algorithm 3 is O(n max(z c )).

Proof We start by proving correctness of the algorithm. We use induction on the length of the sequence. Given f c,j we can reconstruct a corresponding set of sequences S c,j by traversing the table backward.

The base case is trivial as x 1 ∈ P k , f 0,0 = {1, 1} and f c,0 = {∞, ∞}. Suppose the statement holds for j -1 variables.

Case 1. Consider the case x j ∈ P k . Note, that the cost can not be increased on seeing x j ∈ P k as cost only depends on covered undetermined variables. By the induction hypothesis, S c,j-1 satisfies conditions 1-4. The only way to obtain S c,j from S c ,j-1 , c ∈ [0, z U c ], is to extend last(S c,j-1 ) to cover x j or start a new sequence if |last(S c,j-1 )| = len. If S c,j-1 does not exist then S c,j does not exist. The algorithm performs this extension (lines 9 and 10). Hence, S c,j satisfies conditions 1-4.

Case 2. Consider the case x j ∈ U k . In this case, there exist two options to obtain S c,j from from S c ,j-1 , c ∈ [0, z U c ]. The first option is to cover x j . Hence, we need to extend last(S c-1,j-1 ). Note that we should not start a new sequence if last(S c-1,j-1 ) = len as it is never optimal to start a sequence on seeing a neutral variable.

The second option is not to cover x j . Hence, we need to interrupt last(S c,j-1 ). By Lemma 9 we know that f c,j-1 ≤ f c-1,j-1 , 0 < c ≤ C. By the induction hypothesis, S c,j-1 and S c-1,j-1 satisfy conditions 1-4. Hence, S c,j-1 ≤ S c-1,j-1 .

Consider two cases. Suppose |S c,j-1 | < |S c-1,j-1 |. In this case, it is optimal to interrupt last(S c,j-1 ).

Suppose |S c,j-1 | = |S c-1,j-1 | and |last(S c,j-1 )| ≤ |last(S c-1,j-1 )|. If |last(S c-1,j-1 )| < len then it is optimal to extend last(S c-1,j-1 ). If |last(S c-1,j-1 )| = len then it is optimal to interrupt last(S c,j-1 ), otherwise we would have to start a new sequence to cover an undetermined variable x j , which is never optimal. If S c,j-1 and S c-1,j-1 do not exist then S c,j does not exist. If S c,j-1 does not exist then case analysis is similar to the analysis above.

This case-based analysis is exactly what Algorithm 3 does in line 12. Hence, S c,j satisfies conditions 1-4.

Case 3. Consider the case x j ∈ N k . Note that the cost can not be increased on seeing x j ∈ N k as cost only depends on covered undetermined variables. By the induction hypothesis, S c,j-1 satisfies conditions 1-4. The only way to obtain S c,j from S c ,j-1 , c ∈ [0, z U c ], is to interrupt last(S c,j-1 ). If S c,j-1 does not exist then S c,j does not exist. The algorithm performs this extension in line 15. Hence, S c,j satisfies conditions 1-4.

Regarding the worst case time complexity, it is clear that this algorithm requires O(n max(z c )) = O(n 2 ) as we have O(n max(z c )) elements in the table and we only need to inspect a constant number of elements to compute f (c, j).

Proof We build dynamic programming tables f and b. We will show that to check if

x i = v has a support it is sufficient to examine O(z U c ) pairs of values f c1,i-1 and b c2,n-i-2 , c 1 , c 2 ∈ [0, z U c
] which are neighbour columns to the ith column. It is easy to show that if we consider all possible pairs of elements in f c1,i-1 and b c2,n-i-2 then we determine if there exists a support for x i = v. There are O(z U c × z U c ) such pairs. The main part of the proof shows that it sufficient to consider O(z U c ) such pairs. Next, we provide a formal proof.

Consider dynamic programming tables f and b and a variable-value pair x i = v. We will show that to check if

x i = v has a support it is sufficient to examine O(z U c ) pairs of values f c1,i-1 and b c2,n-i-2 , c 1 , c 2 ∈ [0, z U c ].
We introduce two dummy variables x -1 and x n , D(x -1 ) = D(x n ) = 0 to keep uniform notations.

Consider a variable-value pair

x i = v, v > k.
Note that it is sufficient to find a support one value v, v > k as all values greater than k are indistinguishable. Due to Lemma 10 it is sufficient to consider only elements in the neighbouring columns to the ith column in f and b. Namely, the (i -1)th column in f and (n -i -2) in b. The reason for that is that elements in these columns

f c1,i-1 and b c2,n-i-2 , c 1 , c 2 ∈ [0, z U c
] correspond to sets of sequences, S c1,i-1 and S c2,n-i-2 , that are optimal with respect to conditions 1-4 for the prefix [x 0 , . . . , x j-1 ] and the suffix [x j+1 , . . . , x n-1 ], respectively. The main goal is to check whether we can 'glue' the corresponding partial covers S c1,i-1 , S c2,n-i-2 with x i = v into a single cover S over all variables that satisfies the constraint. To glue S c1,i-1 , S c2,n-i-2 and x i = v into a single cover we have few options:

-The first and the most expensive option is to create a new sequence s of length

1 to cover x i . Then the union S = S c1,i-1 ∪ S c2,n-i-2 ∪ {s } forms a cover s.t. cst(S) = c 1 + c 2 + 1 and |S| = |S c1,i-1 | + |S c2,n-i-2 | + 1.
-The second option is to extend last(S c1,i-1 ) to the right by one if |last(S c1,i-1 )| < len. Hence, the updated set S c1,i-1 is identical to S c1,i-1 except the last sequence is increased by one element on the right. Then the union S = S c1,i-1 ∪ S c2,n-i-2 forms a cover: cst(S) = c 1 + c 2 + 1 and

|S| = |S c1,i-1 | + |S c2,n-i-2 |.
-The third option is to extend last(S c2,n-i-2 ) to the left by one if |last(S c2,n-i-2 )| < len. This case is symmetric to the previous case. -The fourth and the cheapest option is to glue last(S c1,i-1 ), x v and last(S c2,n-i-2 ) to a single sequence if |last(S c1,i-1

)| + |last(S c2,n-i-2 )| < len. Hence, S c1,i-1 = S c1,i-1 \ last(S c1,i-1 ), S c2,n-i-2 = S c2,n-i-2 \ last(S c2,n-i-2
) and s is a concatenation of last(S c1,i-1 ), x = v and last(S c2,n-i-2 )]. Then the union S = S c1,i-1 ∪ S c2,n-i-2 ∪ {s } forms a cover:

cst(S) = c 1 + c 2 + 1 and |S| = |S c1,i-1 | + |S c2,n-i-2 | -1.
We can go over all pairs f c1,i-1 and b c2,n-i-2 , c 1 , c 2 ∈ [0, z U c ] and check the four cases above. If obtained cover S is such that cst(S) ≤ z U c and |S| ≤ max(y c ) then we have found a support for x i = v. Otherwise, x i = v does not have a support due to Lemma 10. However, if we need to consider all pairs f c1,i-1 and b

c2,n-i-2 , c 1 , c 2 ∈ [0, z U c ] then finding a support takes O((z U c ) 2 ) time.
We show next that it is sufficient to consider a linear number of pairs. We observe that in all four options above the cost of resulting cover S is c 1 + c 2 + 1. Therefore, we only need to consider pairs f c1,i-1 and b c2,n-i-2 such that c 1 +c 2 +1 ≤ z U c . Therefore, for each f c1,i-1 it is sufficient to consider only one element b c2,n-i-2 such that b c2,n-i-2 is non-dummy and c 2 is the maximum value that satisfies inequality c 1 + c 2 + 1 ≤ z U c . We prove by contradiction. Suppose, there exists a pair f c1,i-1 and b c 2 ,n-i-2 such that c 1 + c 2 + 1 ≤ z U c and S c1,i-1 and S c 2 ,n-i-2 can be extended to a support. However, S c1,i-1 and S c2,n-i-2 can not be extended to a support for

x i = v, c 1 + c 2 + 1 ≤ z U c and c 2 < c 2 . By Lemma 9, we know b c 2 ,n-i-2 ≤ b c2,n-i-2 . However, in this case, |S c1,i-1 | + |S c2,n-i-2 | ≤ |S c1,i-1 | + |S c 2 ,n-i-2 | ≤ max(y c ) + 1.
In the case of equality, we know that last(S c2,n-i-2 ) < last(S c 2 ,n-i-2 ). Hence, if S c1,i-1 and S c 2 ,n-i-2 can be extended to a support then S c1,i-1 and S c2,n-i-2 can be extended to a support. This leads to a contradiction.

Note that we do not need to search for each f c1,i-1 as we can find its pair b c2,n-i-2 in O(1) due to consecutivity property of non-dummy values in each column (Lemma 8). Hence, we need O(z U c ) = O(max(z c )) time to check for support for x i = v.

Consider a variable-value pair

x i = v, v ≤ k.
Note that it is sufficient to find a support for one value v, v ≤ k as all values less than or equal to k are indistinguishable. We again consider all pairs in the neighbouring columns, f c1,i-1 and b c2,n-i-2 and consider how to 'glue' the corresponding partial covers S c1,i-1 , S c2,n-i-2 with x i = v into a single cover S over all variables to satisfy the constraint. In this case, there is only one option to join S c1,i-1 and S c2,n-i-2 . Then union S = S c1,i-1 ∪ S c2,n-i-2 forms a cover:

cst(S) = c 1 + c 2 and |S| = |S c1,i-1 | + |S c2,n-i-2 |. We can go over all pairs f c1,i-1 and b c2,n-i-2 , c 1 , c 2 ∈ [0, z U c ]
to check if such a pair exists. We again show that it is sufficient to consider a linear number of pairs. We observe that in all four options above the cost of resulting cover S is c 1 + c 2 . Therefore, we only need to consider pairs f c1,i-1 and b c2,n-i-2 such that c 1 + c 2 ≤ z U c . Therefore, for each f c1,i-1 it is sufficient to consider only one element b c2,n-i-2 such that b c2,n-i-2 is non-dummy and c 2 is the maximum value that satisfies inequality c 1 + c 2 ≤ z U c . We prove by contradiction. Suppose, there exists a pair f c1,i-1 and b c 2 ,n-i-2 such that c 1 + c 2 ≤ z U c and S c1,i-1 and S c 2 ,n-i-2 can be extended to a support. However, S c1,i-1 and S c2,n-i-2 can not be extended to a support for

x i = v, c 1 + c 2 ≤ z U c and c 2 < c 2 . By Lemma 9, we know b c 2 ,n-i-2 ≤ b c2,n-i-2 . However, in this case, |S c1,i-1 | + |S c2,n-i-2 | ≤ |S c1,i-1 | + |S c 2 ,n-i-2 | ≤ max(y c ).
In the case of equality, we know that last(S c2,n-i-2 ) < last(S c 2 ,n-i-2 ). Hence, if S c1,i-1 and S c 2 ,n-i-2 can be extended to a support then S c1,i-1 and S c2,n-i-2 can be extended to a support. This leads to a contradiction.

Complexity. We compute the tables f and b. Then we check for a support for two values v 1 and v (z c )) time for each variable x i , i = 0, . . . , n -1. Hence, the time complexity to enforce domain consistency is O(n max(z c )).

2 , v 1 ≤ k and v 2 > k, in D(x i ) in O(max
In particular, to check a support for a variable-value pair To check a support for a variable-value pair x i = v, v ≤ k, for each f c1,i-1 it is sufficient to consider only one element b c2,n-i-2 such that b c2,n-i-2 is non-dummy and c 2 is the maximum value that satisfies inequality

x i = v, v > k, for each f c1,i-1 it is sufficient to consider only one element b c2,n-i-2 such that b c2,n-i-2 is non-dummy and c 2 is the maximum value that satisfies inequality c 1 + c 2 + 1 ≤ z U c . D(x 0 ) D(x 1 ) D(x 2 ) D(x 3 ) D(x 4 ) D(x 5 ) D(x 6 ) D(x 7 ) c [1, 1] [0, 1] [1, 1] [1, 1] [0, 1] [1, 1] [0, 1] [1, 1] 0 {4, 1} {3, ∞} {3, 2} {3, 1} {2, ∞} {2, 1} {1, ∞} {1, 1} 1 {3, 1} {2, ∞} {2, 2} {2, 1} {1, ∞} {1, 3} {1, 2} z U c = 2 {2, 4} {2, 3} {2, 1} {1, 5} {1, 4}
c 1 + c 2 ≤ z U c .
Example 9 Table 2 shows an execution of Algorithm 3 on the reversed sequence of variables x of FOCUS from Example 6. Consider, for example, the variable x 4 . To check if x 4 = 1 has as a support we need to consider two pairs:

f 0,3 , b 1,5 and f 1,3 , b 0,5 .
Consider the first pair: (y c ) + 1 = 3, we check whether we can merge last(S 0,3 ), x 4 = 1, and last(S 1,5 ). Hence, |last(S 0,3 )| + |last(S 1,5 )| = 2 + 3 = len = 5. Therefore, we cannot merge last(S 0,3 ), x i = 1 and last(S 1,5 ) into a single sequence s of length 5.

f 0,3 = {2, 2} and b 1,5 = {1, 3}. As |S 0,3 | + |S 1,5 | = 2 + 1 = max
Consider the second pair:

f 1,3 = {1, 4} and b 0,5 = {2, 1}. As |S 1,3 | + |S 0,5 | = 1 + 2 = max(y c ) + 1 = 3, x 4 = 1,
we check whether we can merge last(S 1,3 ) and last(S 0,5 ). As |last(S 1,3 )| + |last(S 0,5 )| = 4 + 1 is equal to len = 5, we cannot merge last(S 1,3 ), x i = 1 and last(S 0,5 ) into a single sequence s of length at most 5. The second pair cannot be used to build a support for x 4 = 1. Hence, x 4 = 1 does not have a support.

To check if x 4 = 0 has as support we need to consider pairs: We observe a useful property of the constraint. If there exists f c,n-1 such that c < max(z c ) and q c,n-1 < max(y c ) then the constraint is BC. This follows from the observation that given a solution of the constraint S X , changing a variable value can increase cst(S X ) and |S X | by at most one.

f 0,
Decomposition with O(n) variables and constraints. Alternatively we can decompose WEIGHTEDFOCUS using O(n) additional variables and constraints.

Given FOCUS(X, y c , len, k ), let z c be a variable and

B=[b 0 , b 1 , . . . , b n-1 ] be a set of variables such that ∀ b l ∈ B, D(b l ) = {0, 1}. We can decompose WEIGHTEDFOCUS as follows: WEIGHTEDFOCUS(X, y c , len, k , z c ) ⇔ FOCUS(X, y c , len, k ) ∧ [∀l, 0 ≤ l < n, [(x l ≤ k ) ∧ (b l = 0)] ∨ [(x l > k ) ∧ (b l = 1)]] ∧ l∈{0,1,...,n-1} b l ≤ z c .
Enforcing BC on each constraint of the decomposition is weaker than BC on WEIGHTEDFOCUS. Given x l ∈ X, a value may have a unique support for FOCUS which violates l∈{0,1,...,n-1} b l ≤ z c , and conversely. Consider n=5, D(x 0 )=D(x 2 )={1}, D(x 3 )={0}, and D(x 1 )=D(x 4 )={0, 1}, D(y c ) = {2}, D(z c ) = {3}, k =0 and len=3. Value 1 for x 4 corresponds to this case. Another interesting approach for solving WEIGHTEDFOCUS is to reformulate it as an integer linear program. If the constructed ILP is tractable as was the case for SPRINGYFOCUS, then we can obtain an alternative filtering algorithm for WEIGHTEDFOCUS. However, the approach that we used in Section 3.3 does not work for WEIGHTEDFOCUS. Recall that in Section 3.3 it was sufficient to consider O(n) possible sequences with distinct starting points. It is essential that sequences have distinct starting points as this ensures that the resulting ILP has the consecutive ones property. By relaxing the disjointness requirement, we used these sequences to find a solution of SPRINGYFOCUSOVERLAP and transform it into a solution of SPRINGYFOCUS. The following example shows that the same approach does not work for WEIGHTEDFOCUS.

Example 10 Consider variables

X = [x 0 , x 1 , . . . , x 5 ] with domains [1, {0, 1}, 1, 1, {0, 1}, 1]
and WEIGHTEDFOCUS(X, [2, 3], 3, 0, [START_REF][END_REF][START_REF] De Clercq | Filtering algorithms for discrete cumulative problems with overloads of resource[END_REF]).

Following approach in Section 3.3, we consider six sequences S o X = {s 0,2 , s 1,3 , s 2,4 , s 3,5 , s 4,6 , s 5,6 , s 6,6 }. The cost of any solution that uses sequences from S o X is 6. However, there exists a solution of WEIGHTEDFOCUS with cost 4: S X = {s 0,1 , s 2,3 , s 5,5 }, y c = 3 and z c = 4.

Weighted Springy FOCUS

We consider a further generalization of the FOCUS constraint that combines SPRINGYFOCUS and WEIGHTEDFOCUS. We prove that we can propagate this constraint in O(n max(z c )) time, which is same as enforcing BC on WEIGHTEDFOCUS.

Definition and Filtering Algorithm

Definition 10 Let y c and z c be two variables and k , len, h be three integers, such that 1 ≤ len ≤ |X| and 0 < h < len -1. An instantiation of X ∪ {y c } ∪ z c satisfies WEIGHTEDSPRINGYFOCUS(X, y c , len, h, k , z c ) iff there exists a set S X of disjoint sequences of indices s i,j such that five conditions are all satisfied:

1. |S X | ≤ y c 2. ∀x l ∈ X, x l > k ⇒ ∃s i,j ∈ S X such that l ∈ s i,j 3. ∀s i,j ∈ S X , |{l ∈ s i,j , x l ≤ k }| ≤ h 4. ∀s i,j ∈ S X , j -i + 1 ≤ len, x i > k and x j > k. 5. si,j ∈S X |s i,j | ≤ z c .
We can again partition cost of S into two terms. si,j ∈S |s i,j | = si,j ∈S cst(s i,j ) + |P k |. However, cst(s i,j ) is the number of undetermined and neutral variables covered s i,j , cst(s i,j ) = |{p|x p ∈ U k ∪ N k , x p ∈ s i,j }| as we allow to cover up to h neutral variables.

The propagator is again based on a dynamic program that for each prefix of variables [x 0 , x 1 , . . . , x j ] and given cost c computes a cover S c,j of minimum cardinality that covers all penalized variables in the prefix [x 0 , x 1 , . . . , x j ] and has cost exactly c. We face the same problem of how to compare two sets S 1 c,j and S 2 c,j of minimum cardinality. The issue here is how to compare last(S 1 c,j ) and last(S 2 c,j ) if they cover a different number of neutral variables. Luckily, we can avoid this problem due to the following monotonicity property. If last(S 1 c,j ) and last(S 2 c,j ) are not equal to infinity then they both end at the same position j. Hence, if last(S 1 c,j ) ≤ last(S 2 c,j ) then the number of neutral variables covered by last(S 1 c,j ) is no larger than the number of neutral variables covered by last(S 2 c,j ). Therefore, we can define order on sets S c,j as we did in Section 4 for WEIGHTEDFOCUS.

Our bounds disentailment detection algorithm for WEIGHTEDSPRINGYFOCUS mimics Algorithm 3. We show a pseudocode for it in Algorithm 4.

Algorithm 4: WEIGHTEDSPRINGYFOCUS(x 0 , . . . , x n-1 )

1 for c ∈ -1..z U c do 2 for j ∈ -1..n -1 do 3 f c,j ← {∞, ∞, ∞}; 4 f 0,-1 ← {0, 0, 0} ; 5 for j ∈ 0..n -1 do 6 for c ∈ 0..j do 7 if x j ∈ P k then / * penalizing * / 8 if (l c,j-1 ∈ [1, len)) ∨ (q c,j-1 = ∞); 9 then 10 f c,j ← {q c,j-1 , l c,j-1 + 1, h c,j-1 }; 11 else 12 f c,j ← {q c,j-1 + 1, 1, 0}; 13 if x j ∈ U k then / * undetermined * / 14 if (l c-1,j-1 ∈ [1, len) ∧ q c-1,j-1 = q c,j-1 ) ∨ (q c,j-1 = ∞); 15 then 16 f c,j ← {q c-1,j-1 , l c-1,j-1 + 1, h c-1,j-1 }; 17 else 18 f c,j ← {q c,j-1 , ∞, ∞} ; 19 if x j ∈ N k then / * neutral * / 20 if (l c-1,j-1 ∈ [1, len) ∧ h c-1,j-1 ∈ [1, h) ∧ q c-1,j-1 = q c,j-1 ) ∨ (q c,j-1 = ∞); 21 then 22 f c,j ← {q c-1,j-1 , l c-1,j-1 + 1, h c-1,j-1 + 1}; 23 else 24 f c,j ← {q c,j-1 , ∞, ∞} ; 25 return f ;
We highlight two non-trivial differences between Algorithm 4 and Algorithm 3. The first difference is that each cell in the dynamic programming table

f c,j , c ∈ [0, z U c ], j ∈ {0, 1, . . . , n -1}, where z U c = max(z c ) -|P k |
, is a triple of values q c,j , l c,j and h c,j , f c,j = {q c,j , l c,j , h c,j }. The new parameter h c,j stores the number of neutral variables covered by last(S c,j ). The second difference is in the way we deal with neutral variables. If x j ∈ N k then we have two options now. We can obtain S c,j from S c-1,j-1 by increasing cst(S c-1,j-1 ) by one and increasing the number of covered neutral variables by last(S c,j-1 ) (Figure 4(c), the gray arc). Alternatively, we can obtain S c,j from S c,j-1 by interrupting last(S c,j-1 ) (Figure 4(c), the black arc). BC can be enforced using two modifications of the corresponding algorithm for WEIGHTEDFOCUS Lemma 12 Consider WEIGHTEDSPRINGYFOCUS(X, y c , len, h, k , z c ). BC can be enforced in O(n max(z c )) time.

Proof The main idea is identical to the proof of the WEIGHTEDFOCUS constraint. We only highlight the differences between the WEIGHTEDFOCUS constraint and the WEIGHTEDSPRINGYFOCUS constraint.

Consider a variable-value pair

x i = v, v > k.
The only difference is in the fourth option. We denote h(s i,j ) the number of neutral variables covered by s i,j . Similarly, h(S) = s i,j∈S h(s i,j ).

-The fourth and the cheapest option is to glue last(S c1,i-1 ), x v and last(S c2,n-i-2 ) to a single sequence if |last(S c1,i-1 )|+|last(S c2,n-i-2 )| < len and h(last(S c1,i-1

)) + h(last(S c2,n-i-2 )) ≤ h. Hence, S c1,i-1 = S c1,i-1 \ last(S c1,i-1 ), S c2,n-i-2 = S c2,n-i-2 \ last(S c2,n-i-2
) and s is a concatenation of last(S c1,i-1 ), x = v and last(S c2,n-i-2 )]. Then the union S = S c1,i-1 ∪ S c2,n-i-2 ∪ {s } forms a cover:

cst(S) = c 1 + c 2 + 1, |S| = |S c1,i-1 | + |S c2,n-i-2 | -1 and h(S) = h(last(S c1,i-1 )) + h(last(S c2,n-i-2 )).
The rest of the proof is analogous to WEIGHTEDFOCUS. Consider a variable-value pair

x i = v, v ≤ k.
The main difference is that we have the second option to build a support. Namely, we glue S c1,i-1 , x i and S c2,n-i-2 . Hence, if c 1 +c 2 +1 ≤ z U c , |last(S c1,i-1 )|+|last(S c2,n-i-2 )| < len and h(last(S c1,i-1 )) + h(last(S c2,n-i-2 )) < h then we can build a support for x i = v. The rest of the proof is analogous to WEIGHTEDFOCUS.

Decomposition

WEIGHTEDSPRINGYFOCUS can be encoded using the cost-REGULAR constraint [START_REF] Demassey | A cost-regular based hybrid column generation approach[END_REF]. Indeed, one can use two states 0 and 1 (in addition to the initial state) as follows. The state 0 captures all values v ≤ k not included in any subsequence in S X . The set of states 1 captures the values belonging to a subsequence in S X . The transition between 0 and 1 is quite straightforward following the semantic of WEIGHTEDSPRINGYFOCUS, however, the automaton is non-deterministic as on seeing v ≤ k in 1 , it either covers the variable or interrupts the last sequence. The automaton needs 3 counters to compute len, y c and h. Hence, the time complexity of this encoding is O(n 4 ). Unfortunately the non-deterministic cost-REGULAR is not implemented in any constraint solver to our knowledge. In fact REGULAR [START_REF] Pesant | A Regular Language Membership Constraint for Finite Sequences of Variables[END_REF] and cost-REGULAR [START_REF] Demassey | A cost-regular based hybrid column generation approach[END_REF] are defined only with deterministic automatons. A possible way to deal with our non-deterministic situation is to transform it into a deterministic automaton. However this transformation is known to be exponential in the worst case.

The worst case time complexity O(n 4 ) is likely to get worse, however, domain consistency is guaranteed. In contrast, our algorithm takes just O(n 2 ) time.

WEIGHTEDSPRINGYFOCUS can also be decomposed using the GCC constraint [START_REF] Régin | Generalized arc consistency for global cardinality constraint[END_REF]. We define the following variables for all i ∈ [0, max(y c )-1] and j ∈ [0, n-1]: S i the start of the ith sub-sequence. D(S i ) = {0, .., n + max(y c )}; E i the end of the ith sub-sequence. D(E i ) = {0, .., n + max(y c )}; T j the index of the subsequence in S X containing x j . D(T j ) = {0, .., max(y c )}; Z j the index of the subsequence in S X containing x j s.t. the value of x j is less than or equal to k. D(Z j ) = {0, .., max(y c )}; last c the cardinality of S X . D(last c ) = {0, .., max(y c )}; Card, a vector of max(y c ) variables having {0, .., h} as domains.

WEIGHTEDSPRINGYFOCUS(X, y c , len, h, k , z c ) ⇔

(x j ≤ k ) ∨ Z j = 0; (x j ≤ k ) ∨ T j > 0; (x j > k ) ∨ (T j = Z j ); (T j ≤ last c ); (T j = i) ∨ (j ≥ S i-1 ); (T j = i) ∨ (j ≤ E i-1 ); (i > last c ) ∨ (T j = i)∨(j < S i-1 ) ∨ (j > E i-1 ); ∀q ∈ [1, max(y c ) -1] : q ≥ last c ∨ S q > E q-1 ; ∀q ∈ [0, max(y c ) -1] : q ≥ last c ∨ E q ≥ S q ; ∀q ∈ [0, max(y c ) -1] : q ≥ last c ∨ len > (E q -S q ); last c ≤ y c ; Gcc([T 0 , .., T n-1 ], {0}, [n -z c ]); Gcc([Z 0 , .., Z n-1 ], {1, .., max(y c )}, Card);
The main advantage of this decomposition is that it uses constraints that are available in most existing solvers. However, it hinders propagation, that is, Bound Consistency is no longer guaranteed. Consider the same example showing that WEIGHTEDFOCUS is stronger than the first decomposition using FOCUS.Let n=5, h=0, k =0, len=3, D(x 0 )=D(x 2 )={1}, D(x 3 )={0}, D(x 1 )=D(x 4 )={0, 1}, D(y c ) = {2}, and D(z c ) = {3}. Enforcing Bound Consistency using the above decomposition will keep the domain of x 4 equal to {0, 1} whereas the value 1 has no support.

Experiments

Protocol

We use the Choco-2.1.5 solver on Intel Xeon E5-2640 processors (2.50GHz) under Linux. The source code as well as the reproduction steps are available at http://siala.github.io/focus/focus-details.pdf. We compare the propagators of our global constraints (denoted by F) of WEIGHTEDFOCUS and WEIGHTEDSPRINGYFOCUS against two decompositions with generic constraints (denoted by D 1 and D 2 ). For each benchmark, the comparison is performed using the same search strategies for the different constraint models. The first decomposition (D 1 ) is restricted to WEIGHTEDFOCUS and uses FOCUS as we explained in section 4.

Te second decomposition (D 2 ) is shown in Section 5.2 and uses constraints available in most CP solvers (such as GCC ). We do not present experiments for the propagator of SPRINGYFOCUS because this propagator is linear in the number of variables and does not involve complex data structures, which leads to a behaviour similar to the case of FOCUS (see [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]). Although it makes an interesting connection between ILP and our framework, the ILP formulation of SPRINGYFOCUS cannot outperform this propagator.

We use the following presentation protocol for all tables. First, we give the number of solved instances (#sol). Then, we report the CPU time (Time), the number of nodes (Nodes), and the speed of exploration in terms of nodes explored per second (Nodes/s). In particular, we report the average (avg.) and the standard deviation (dev.) for these statistics across all successful runs. The best results are shown with bold face fonts w.r.t. the number of solutions (#sol).

Sports league scheduling (SLS)

We extend a single round-robin problem with n = 2p teams. Each week each team plays a game either at home or away. Each team plays exactly once all the other teams during a half-season (in practice, the second half of the season is symmetric). We minimize the number of breaks (a break for one team is two consecutive home or two consecutive away games), while fixed weights in {0, 1} are assigned to all games: games with weight 1 are important for TV channels. The goal is to group consecutive weeks where at least one game is important (sum of weights > 0), to increase the price of TV broadcast packages. Packages are limited to 5 weeks and should be as short as possible. These requirements are expressed either using WEIGHTEDFOCUS or using its decomposition. The concentration of important matches into packages is obtained by minimizing y c , while for each such value of y c we obtain the global minimum length for packages by minimizing the sum of lengths.

Model. In our model, inverse-channelling and ALLDIFFERENT constraints with the strongest propagation level express that each team plays once against each other team. With respect to the sport scheduling part (independently from the weights and WEIGHTEDFOCUS constraint or its decomposition), our model is inspired from Régin's paper on sport league scheduling [START_REF] Régin | Minimization of the number of breaks in sports scheduling problems using constraint programming[END_REF], although some differences exist, in order to best fit with the available propagators of Choco-2.1.5. A pseudo-code of the model of the whole problem is provided in Figure 5. We use the procedure getColumn(Integer[][] m, k) for extracting the k th column of the matrix given as argument.

Search strategy. We use the following search strategy: assign first the sum of breaks by team, then the breaks and then the places, using for each group the DomOverWDeg variable selection strategy with the lowest values assigned first. We fix the matches of the first team and then minimize z c while the number of breaks is at its theoretical minimum (n -2) and we arbitrary fix the maximum value of y c .

In our context, using DomOverWDeg does not affect the comparison between the decomposition and the global constraint approach. Using a static search strategy leads to poor results concerning the sport league scheduling part of the problem, but this part is common to the decomposition and the global constraint models. Regarding TV broadcast packages, the results with WEIGHTEDFOCUS are almost the same with DomOverWDeg and if we use a static search strategy for the variables expressing weights and sum of weights. Using the decomposition approach, the results are better with DomOverWDeg. We present the results obtained for each model using DomOverWDeg in Table 3 and using a static branching (lexicographic exploration with minimum value) in Table 4 .

We consider the results with 16, 18, and 20 teams, on sets of 50 instances with 10 random important games and a limit of 400K backtracks. max(y c ) = 3 and we search for one solution with h ≤ 7 (instances n-1), h ≤ 6 (n-2) and h ≤ 5 (n-3). Note that the models with 18 and 20 teams are not shown in Table 4 because no solution was found with the static branching.

Table 3 shows clearly that the model using the global propagator dominates the decomposition on this problem. The difference of resolved instances between the two models increases with the instance size. For example with instances 20 3 the filtering algorithm solves 39 instances out of 50 whereas the decomposition solves only 29 of the instances. The new filtering does not require additional amount of time, and in fact it is faster than the average CPU time of the decomposition in general1 . There are many cases where the shape of the search tree differs between the two methods in terms of nodes. For instance, with 18 1, enforcing domain consistency deplores 1876 nodes whereas the decomposition explores at least three times this number (i.e. 6040). The extra filtering of the global constraint does help a lot by pruning more unsatisfiable subtrees which guides the heuristic towards solutions. It should be noted, however, that the decomposition explores faster the search tree. This behaviour is expected as decomposition leads to simpler filtering that is likely to be faster in general. It should be noted also that the standard deviation in almost all the cases was smaller with the complete filtering. Regarding the results with the static branching, one can confirm that the models behave poorly as expected (Table 4). However, the performances trend is the same. More importantly, the results of the complete filtering are more robust than the decomposition. Take for instance the results of 16 2. The standard deviation of the nodes is 37 using the global constraint and 1749 using the decomposition. Given a horizon of n days and a set of time intervals [s i , e i ], i ∈ {1, 2, . . . , p}, a company needs to rent a machine between l i and u i times within each time interval [s i , e i ]. We assume that the cost of the rental period is proportional to its length. On top of this, each time the machine is rented we pay a fixed cost.

Model. The problem is stated in a very simple way by bucketing time with {0,1} variables indicating whether a machine is rented or not for covering this time point. We define a conjunction of one WEIGHTEDSPRINGYFOCUS(X, y c , len, h, 0, z c ) with a set of AMONG constraints. The decision version of the problem is presented in Figure 6. The goal is to build a schedule for rentals that satisfies all demand constraints and minimizes simultaneously the number of rental periods and their total length. Therefore, we build a Pareto frontier over two cost variables, as Figure 7 shows for one of the instances of this problem. More specifically, we start by minimizing y c , then immediately try to minimize z c while fixing y c to its minimum. Afterwards, we repeatedly increment y c by 1 then try to find the correspondent minimal value of z c . The process stops when either a maximum number of iterations is reached or no improvement on z c is obtained. Figure 7 confirms the gain of flexibility illustrated by Figure 1 in Section 3: allowing h = 1 variable with a low cost value into each sequence leads to new solutions, with significantly lower values for the target variable y c .

We generated instances having a fixed length of sub-sequences of size 20 (i.e., len = 20), 50% as a probability of posting an Among constraint for each (i, j) s.t. j ≥ i + 5 in the sequence. Each set of instances corresponds to a unique sequence size ({40, 43, 45, 47, 50}) with 20 different seeds.

We summarize these tests in Tables 5 and6. Results with decomposition are very poor. We therefore do not show them in these tables. The performances in this problem with DomOverWDeg are very similar to the sports league scheduling problem. The global filtering completely outperforms the decomposition with GCC as we said. Regarding the first decomposition (D 1 ), it behaves relatively well on the first four sets 40, 43, 45, 47 and slightly worse than the global constraint in the set 50 (i.e. only 14 solved instances compared to 17 instances with F). Using the static branching on this particular problem was very beneficial. There is no significant performance differences betweens the two models F and D 1 . Indeed, they find the same number of solution in all instances with h = 0. The average runtime is slightly but constantly better with the global filtering. The number of nodes is also smaller. However, overall, there was no significant difference between the two models. It should be noted that in both branching strategies, the standard deviation is better with the global constraint than the decomposition.

Sorting Chords

We need to sort n distinct chords. Each chord is a set of at most p notes played simultaneously. The goal is to find an ordering that minimizes the number of notes changing between two consecutive chords.

Model. The full description and a CP model is in [START_REF] Petit | Focus: A constraint for concentrating high costs[END_REF]. Figure 6.4 provides a pseudocode for this problem. The main difference here is that instead of minimizing either z c or y c , we build a Pareto frontier over these two cost variables (the same way performed with the previous benchmark), using WEIGHTEDSPRINGYFOCUS and its decompositions. We generated 4 sets of instances distinguished by the numbers of chords ({14, 16, 18, 20}). We fixed the length of the subsequences and the maximum notes for all the sets then changed the seed for each instance.

Search strategy. As in the Sports League Scheduling benchmark, we present the results obtained for each model, i.e., the model that uses WEIGHTEDSPRINGYFOCUS and the models with its decompositions. The search strategy is DomOverWDeg with the lowest values assigned first (Table 7). The static branching performs very poorly on these instances and is therefore not shown here.

The main observation from Table 7 is that when h = 0, the first decomposition D 1 performs as good as the complete filtering in general. With 16 and 18 chords, D 1 finds an additional solution compared to the complete filtering F. The average nodes, and the average nodes explored per second are very similar in both models. The standard deviation is also very similar with all statics in general. The decomposition using GCC performs much better than the previous problem but it is outperformed by WEIGHTEDSPRINGYFOCUS. For example, on instances with h = 2 using 18 chords, it finds 9 solutions whereas the complete filtering finds 25.

Conclusion

We have presented flexible tools for capturing the concept of concentrating costs. Our contribution highlights the expressive power of constraint programming, in comparison with other paradigms where such a concept would be very difficult to represent.

We have shown a connection between our constraint and ILP. Our experiments have demonstrated the effectiveness of the proposed new filtering algorithms.

Fig. 1

 1 Fig. 1 Introducing SPRINGYFOCUS Example of a resource with capacity equal to 3. Each day is represented by one unit in the horizontal axis. The capacity usage is represented by the vertical axis. (A) Problem with 4 fixed activities: activity 1 scheduled on day 0 with 4 units of capacity; activity 2 scheduled on day 1 with 2 units of capacity; activity 3 scheduled on day 2 with 4 units of capacity; and activity 4 scheduled on days 3 and 4 with 2 units of capacity each. An additional activity of length 5 should start from time 1 to 5 (i.e. the domain of the starting time of the new activity is D(st)=[1,5]). (B) Solution satisfying FOCUS(X, [1, 1], 5, 3), with a new machine rented for 5 days. (C) Practical solution violating FOCUS(X, [1, 1], 5, 3), with a new machine rented for 3 days but not used on the second day.

Definition 6

 6 card (x l ) is the minimum number of values v ≤ k in the current sequence in S [x0,x1,...,x l ] , equal to 0 if ∀s i,j ∈ S [x0,x1,...,x l ] , j = l. card (x l ) assumes that x l > k. It has to be decreased it by one if x l ≤ k.

Fig. 2

 2 Fig. 2 The set of possible sequences in S X from Example 2.

Fig. 3

 3 Fig. 3 The same initial configuration of Figure 1 (A) Problem with 4 fixed activities and one activity of length 5 that can start from time 3 to 5 (i.e., D(st)=[3,5]). We assume D(yc) = {2}, len = 3 and k = 0. (B) Solution satisfying WEIGHTEDFOCUS with zc = 4. (C) Solution satisfying WEIGHTEDFOCUS with zc = 2.

13 elseFig. 4

 134 Fig. 4 Representation of one step of Algorithm 3.

3 , b 2 , 5

 325 and f 1,3 , b 1,5 . Consider the first pair: f 0,3 = {2, 2} and b 2,5 = {2, 1}. We have |S 0,3 |+|S 2,5 | = 2 + 2 = max(y c ) = 4. Hence, x 4 = 0 has a support.

Fig. 5

 5 Fig. 5 Model of the SLS benchmark.

Fig. 6

 6 Fig. 6 Model of the Cumulative Scheduling with Rentals problem

Fig. 7

 7 Fig. 7 Pareto frontier for Scheduling with Rentals.

Fig. 8

 8 Fig. 8 Model of the Sorting Chords benchmark.

Table 2

 2 An execution of Algorithm 3 on the reverse sequence of variables in WEIGHTEDFOCUS from Example 6. Dummy values b c,j are removed.

Table 3

 3 SLS with WEIGHTEDFOCUS and its decomposition using DomOverWDeg.

				16 1				16 2			16 3
	#sol Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s
		avg. dev. avg. dev. avg. dev.	avg. dev. avg. dev. avg. dev.	avg. dev. avg. dev. avg. dev.
	F 50 0.4 1.1 555 1450 1437 187 50 0.03 3.1 2271 4163 1339 159 47 7.4 16 9679 21555 1270 124
	D 1 50 0.9 3.7 2549 12488 1578 434 49 2.8 6.9 4965 13118 1455 347 44 8.5 16.5 12702 25728 1300 186
				18 1				18 2			18 3
	#sol Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s
		avg. dev. avg. dev. avg. dev.	avg. dev. avg. dev. avg. dev.		avg. dev. avg. dev. avg. dev.
	F 49 2	7 1876 6460 1050 157 49 7.8 16.3 8921 23642 1026 176 42 12 16 12062 17158 946
	D 1 49 3.6 9.5 6040 16230 1290 432 46 9.7 16.3 15063 31795 1207 412 37 11.5 14.7 12648 16097 1022
				20 1				20 2			20 3
	#sol	Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s
		avg. dev. avg. dev. avg. dev.		avg. dev. avg. dev. avg. dev.		avg. dev. avg. dev. avg. dev.
	F 49 7.5 15.2 6265 12237 866 174 45 15.5 21.1 13576 20727 827 121 39 23.7 28.2 19274 22659 828
	D 1 43 14.1 35 19879 54977 1013 318 35 13.2 18393 17318 28917 1017 277 29 18.2 22.7 16373 20769 861 126

Table 4

 4 SLS with WEIGHTEDFOCUS and its decomposition using a static branching.

			16 1				16 2	16 3
	#sol Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s
	avg. dev. avg. dev. avg. dev.	avg. dev. avg. dev. avg. dev.	avg. dev. avg. dev. avg. dev.
	F 23 0	0 6553 39 7144 1353 15 0	0 3911 37 6346 750 7	0	0 1673 31 5741 983
	D 1 21 0	0 6505 51 7115 1885 13 0.3 1 10538 1749 6423 2191 7 0.5 1.1 7168 1917 5043 1660

Table 5

 5 Scheduling with rentals using DomOverWDeg Int n; // number chords, indexed from 0 to n -1 Int[][] costMatrix ; // size: n × n, matrix of costs between pairs of chords Int len, h, k ; // WEIGHTEDSPRINGYFOCUS MODEL: IntVar[] Chords; // size: n, domain {0, 1, . . . , n -1} IntVar[] Costs; // size: n -1, domain: all possible costs Int nChange; // threshold from which a cost is considered as high IntVar yc, zc; // WEIGHTEDSPRINGYFOCUS ∀i ∈ 0..n -2, TABLE(Chords[i], Chords[i + 1], Costs[i]); // cost of each pair ALLDIFFERENT(Chords); WEIGHTEDSPRINGYFOCUS(Costs, yc, len, h, k , zc);

			40						43
	#sol	Time	Nodes	Nodes/s #sol Time	Nodes	Nodes/s
		avg. dev. avg.	dev. avg. dev.	avg. dev. avg.	dev.	avg. dev.
						h=0
	F 20 40 122 135018 423579 1041 869 20 90 269 259805 800815 872 574
	D 1 20 59.09 210 212629 769672 1092 847 20 119 391 372541 1271169 937 665
						h=1
	F 20 95 176 341394 640856 2844 2300 20 252 689 801909 2235387 2556 1769
						h=2
	F 20 96 179 341134 631228 2792 2354 20 257 665 815084 2191171 2560 1791
			45						47
	#sol	Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s
	avg. dev.	avg.	dev.	avg. dev.	avg. dev.	avg.	dev.	avg. dev.
						h=0
	F 20 212 960 565173 2507057 853 701 20 326 547 779999 1300376 716 223
	D 1 20 295 1405 840967 4006454 900 723 20 419 740 1038147 1876769 748 309
						h=1
	F 20 568 1455 1642111 3989712 2613 2598 19 1070 1744 2862135 4794331 2568 2180
						h=2
	F 20 594 1380 1696763 3797544 2588 2467 19 1119 1767 2978121 4621013 2561 2125
						50
			#sol	Time	Nodes	Nodes/s
				avg. dev.	avg.	dev.	avg. dev.
						h=0
			F 17 645 1444 1383185 3029220 676 329
			D 1 14 649 947 1425712 2075470 691 295
						h=1
			F 11 1534 1362 3774669 3020671 2448 1401
						h=2
			F 11 1618 1964 3953820 4409741 2431 1382
	INPUT:

Table 6

 6 Scheduling with rentals using a static branching

			40					43
	#sol Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s
		avg. dev. avg.	dev. avg. dev.		avg. dev.	avg.	dev.	avg. dev.
					h=0
	F 20 13 27 60378 139508 1239 1147 20 25 60	98351 262913 1089 871
	D 1 20 16 31 80002 169747 1393 1210 20 30 75 133450 344122 1223 902
					h=1
	F 20 83 118 349495 522644 3096 2595 20 284 1021 1102987 4530456 2787 1803
					h=2
	F 20 83 118 349488 522638 3103 2575 20 285 1038 1102980 4530356 2791 1849
			45					47
	#sol	Time	Nodes	Nodes/s #sol	Time	Nodes	Nodes/s
		avg. dev. avg.	dev.	avg. dev.	avg. dev. avg.	dev.	avg. dev.
					h=0
	F 20 68 220 260331 882753 1094 930 20 91 213 309481 783447 932 396
	D 1 20 85 276 352155 1149913 1235 965 20 110 264 428014 1110529 1078 501
					h=1
	F 18 1037 631 3723494 2163719 2976 749 2 1205 202 3935339 865505 2560 743
					h=2
	F 18 1041 638 3723480 2163748 2977 772 2 1207 203 3935354 865522 2584 760
						50
				#sol Time	Nodes	Nodes/s
				avg. dev. avg.	dev.	avg. dev.
					h=0
			F 20 216 563 650832 1775355 893 728
			D 1 20 260 688 895516 2461464 1035 811

Table 7

 7 Sorting Chords

				14					16
	#sol Time	Nodes	Nodes/s	#sol Time	Nodes	Nodes/s
		avg. dev. avg.	dev. avg. dev.		avg. dev. avg.	dev.	avg. dev.
						h=0
	F 30 2	7 17577 73168 2923 5350 29 4 13 29963 109164 2737 3655
	D 1 30 2	6 15072 55030 2920 4841 30 5 14 35702 117407 2968 3604
	D 2 30 27 127 154422 739803 2437 3681 20 24 97 125863 522175 2380 2222
						h=1
	F 30 2 12 16224 112110 3707 12269 30 75 980 698888 10086454 4430 13202
	D 2 30 29 135 144228 682095 2252 3268 20 28 112 125375 526964 2107 2029
						h=2
	F 30 2 12 17237 112323 3649 12000 29 31 243 249125 2121349 3883 10085
	D 2 30 31 146 157560 752363 2223 3230 20 29 112 134773 549205 2163 1964
				18					20
	#sol	Time		Nodes	Nodes/s		#sol	Time	Nodes	Nodes/s
		avg. dev.	avg.	dev.	avg. dev.			avg. dev.	avg.	dev.	avg. dev.
						h=0
	F 24 23 80 117113 417085 2022 1864 10 639 2233 3415012 12383754 2849
	D 1 25 59 206 337787 1213605 2283 2406	9 666 1727 3534231 9344656 3023
	D 2 9 235 837 926145 3357408 1660 1594	3 252 572 844450 1877702 2202 982
						h=1
	F 24 397 2345 2500105 15264782 4123 9485	9 444 1109 2257348 6036524 3023
	D 2 9 263 931 947522 3425814 1527 1199	3 284 674 859046 2017445 1932 855
						h=2
	F 25 336 1709 2122557 11238548 4468 11413 11 607 1719 3187854 9777345 2937
	D 2 9 223 703 804368 2637317 1482 1248	4 384 728 1091963 2074681 1805

Recall that the average CPU includes only the runtime of the successful runs.

Example 8 Table 1 shows an execution of Algorithm 3 on WEIGHTEDFOCUS from Example 6. Note that

As can be seen from the table, the constraint has a solution as there exists a set S 2,7 = {s 0,3 , s 5,7 } such that |S 2,7 | = 2. Bounds consistency To enforce BC on the sequence

on the reverse sequence of variables (i.e. [x n-1 , . . . , x 1 , x 0 ]).

Lemma 11 Consider WEIGHTEDFOCUS(X, y c , len, k , z c ). Bounds consistency can be enforced in O(n max(z c )) time.