Philippe Vismara
email: philippe.vismara@supagro.fr

Nicolas Briot

A Circuit Constraint for Multiple Tours Problems

Routing problems appear in many practical applications. In the context of Constraint Programming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem or the Vehicle Routing Problem. These kind of constraints are linked to the search for a Hamiltonian circuit in a graph. In this paper we consider a more general multiple tour problem that consists in covering a part of the graph with a set of minimal cost circuits. We define a new global constraint WeightedSubCircuits that generalizes the WeightedCircuit constraint by releasing the need to obtain a Hamiltonian circuit. It enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph, the subsets of vertices to be covered being induced by external constraints. We show that enforcing Bounds Consistency for WeightedSubCircuits is NP-hard. We propose an incomplete but polynomial filtering method based on the search for a lower bound of a weighted Steiner circuit.

Introduction

Many real problems can be modeled as a tour problem, the best known is the Travelling Salesman Problem (TSP). It consists in finding a Hamiltonian cycle (i.e., passing by each vertex of a graph once) with a minimum weight. Many works coming from Integer Linear Programming (ILP) or dynamic programming allow to quickly solve large instances of TSP. In addition, some variations of the TSP, such as the Vehicle Routing problem (VRP), have been the subject of numerous studies proposing effective solving methods [START_REF] Toth | Vehicle routing: problems, methods, and applications[END_REF].

In this context, Constraint Programming has for a long time offered its expressiveness to address variations of TSP. Initially limited to small instances, the most recent filtering algorithms allow to compete with ILP approaches on complex problems where complementary constraints restrict TSP solutions.

These good results are related to the definition of global constraints and the associated filtering algorithms: the constraint Cycle (or Circuit) enforces covering the graph with one circuit visiting all vertices once; the constraint WeightedCircuit imposes, in addition, that the sum of the costs of the edges of the circuit is lower than a cost variable. As enforcing arc consistency for these constraints is generally NP-hard, the filterings used are inevitably incomplete but in practice relatively efficient. For instance, the WeightedCircuit constraint propagator can incorporate different methods based on TSP relaxation from literature.

However, all these constraints are linked to the search for a Hamiltonian cycle. Many real problems require searching for one or more cycles covering all or part of the vertices of the graph. These problems correspond to two kinds of relaxation in the definition of the Hamiltonian cycle. The classical relaxation is the VRP where some vertices (depots) can be visited several times. This problem is generally modeled by duplicating a few vertices in order to return to a Hamiltonian cycle. The second relaxation consists in not covering all the vertices of the graph, the set of the discarded vertices depending on external constraints. In this case, the Cycle constraint can eventually be used by artificially adding the discarded vertices to the end of the Hamiltonian cycle. However, it becomes impossible to integrate them into a weighted cycle without disrupting the cost of the solution. It is then impossible to benefit from all the filtering power of constraint WeightedCircuit.

In this paper, we aim to generalize the WeightedCircuit constraint in case some vertices can be discarded. We consider a more general multiple tour problem that consists in covering a part of the graph by a set of minimal cost circuits. We define a new global constraint, called WeightedSubCircuits, that enforces multiple disjoint circuits of bounded cost to partially cover a weighted graph. This is a generalization of constraint WeightedCircuit where the Hamiltonian circuit can be divided into several disjointed subcircuits, with an additional subset of discarded vertices.

The remainder of this paper is structured as follows. Section 2 surveys the necessary preliminaries. Section 3 covers related work on global constraints for tour problems. Section 4 gives the definition of WeightedSubCircuits constraint and proposes a decomposition of the constraint with standard constraints and a cycle constraint adapted to multiple tours. Section 5 deals with the filtering of this NoSubTours constraint and that of the WeightedSubCircuits constraint. Finally, Section 6 presents some preliminary experimental results.

Preliminaries

We consider a weighted graph G = (V, E, c) where V is a set of vertices, E a set of edges and a weight function c :

E → Q + .
When the graph G respects triangle inequality, the weight of any edge (i, j) is smaller or equal to the cost of any path from i to j.

Graphs are considered from an oriented point of view. In this context, the term circuit should be used rather than cycle. However, a cycle is generally described by a sequence of vertices or by defining, for each vertex i, the N ext i vertex that follows i in the cycle. In both cases, the cycle is oriented and then it is a circuit.

An elementary circuit of G is a circuit where no vertex appears more than once. A Hamiltonian circuit is an elementary circuit of length |V |.

For any subset W ⊆ V , G[W ] is the subgraph of G induced by W .

For any set variable Set, the lower (respectively upper) bound of Set, denoted by lb(Set) (respectively ub(Set)), is the set of required (respectively possible) values in Set.

In the following, we will note OP T T SP (G) the cost of an optimal solution for T SP (G).

Related work

The Constraint Programming research community has long been interested in the search for Hamiltonian circuits, which were already part of the Alice language constraints [START_REF] Laurière | A language and a program for stating and solving combinatorial problems[END_REF]. A configurable Cycle constraint was also part of the global constraints introduced in the CHIP solver [START_REF] Beldiceanu | Introducing global constraints in chip[END_REF].

The most common model is to define a variable N ext i for each vertex i of the graph, where N ext i represents the vertex which follows i in the Hamiltonian circuit. To ensure that each vertex is visited only once, an AllDifferent constraint can be posted on the N ext i and enforcing GAC for this constraint is polynomial [START_REF] Régin | a filtering algorithm for constraints of difference in CSPs[END_REF]. Conversely, checking that there is a Hamiltonian circuit is NPcomplete. The filtering used in solvers for the Circuit constraint is, therefore, naturally incomplete. Two subconstraints are mainly used for this filtering on the edges composing the circuit: the NoSubTour constraint which prohibits the presence of subcircuits and the Connected constraint which ensures the strong connectivity of the circuit. Other works have proposed a filtering based on graph separators [START_REF] Kaya | A filter for the circuit constraint[END_REF] or investigated how to add explanations to the Circuit constraint in a lazy clause generation solver [START_REF] Francis | Explaining circuit propagation[END_REF].

The NoSubTour constraint [START_REF] Caseau | Solving small tsps with constraints[END_REF][START_REF] Pesant | An exact constraint logic programming algorithm for the traveling salesman problem with time windows[END_REF] is posted on graph G = (V, E). It ensures that the N ext i variables do not form a subtour of length strictly smaller than |V |. Combined with constraint AllDifferent, the NoSubTour constraint enforces N ext i variables to form a Hamiltonian circuit of G.

The filtering generally associated with the NoSubTour constraint consists in removing from N ext i any value that could close a path to form a subcircuit strictly smaller than |V |. This is based on the following rule (Figure 1) applied when N ext i is instantiated with j:

N ext i = j ∧ (L(β(i)) + L(j) + 1) < |V | -1 ⇒ N ext ε(j) = β(i) (1.1)
where, for any vertex z, β(z), ε(z) and L(z) are respectively the begining, the end and the length of the path induced by the N ext i variables and passing through z. Due to constraint AllDifferent, we must have ε(i) = i and β(j) = j when N ext i is instantiated with j.

The values of β(z), ε(z) and L(z) can be easily managed with backtrackable variables and updated in O(1) for each instantiation of N ext z .

β(j) β(i) i j ε(i) ε(j) L(β(i)) L(j) 1 + + < |V | -1
Fig. 1. Illustration of the filtering rule for the NoSubTour constraint.

The Connected constraint has been less studied in literature. The simplest approach is to use a O(|V | + |E|) search algorithm (like Tarjan's) to find strong connected components [START_REF] Dooms | The CP(Graph) Computation Domain in Constraint Programming[END_REF]. It is also possible to limit the number of searches by maintaining a spanning tree [START_REF] Prosser | A connectivity constraint using bridges[END_REF].

Whatever the filtering used for the Circuit constraint, it is only concerned with the connectivity of the graph without taking into account the edge weights. However, the cost of the circuit is a key element in the optimization of a TSP or VRP. Therefore, constraint WeightedCircuit(N ext 1 , . . . , N ext n , Cost) has been defined to enforce the rule that the circuit defined by the variables N ext i has a lower cost than the variable Cost.

The filtering algorithms used for constraint WeightedCircuit are based on TSP relaxations. This consists in reducing the TSP to a polynomial optimization problem whose optimal cost is a lower bound of the initial TSP cost. This bound can be used directly to update lb(Cost). It also filters the N ext i variables by eliminating the edges which are not part of the optimal solution and which, if they replace an edge of this solution, generate an additional cost beyond ub(Cost).

Several relaxations can be used to filter the constraint WeightedCircuit [START_REF] Caseau | Solving small tsps with constraints[END_REF][START_REF] Pesant | An exact constraint logic programming algorithm for the traveling salesman problem with time windows[END_REF][START_REF] Focacci | A hybrid exact algorithm for the TSPTW[END_REF][START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF] and most of them are incomparable [START_REF] Ducomman | Alternative filtering for the weighted circuit constraint: Comparing lower bounds for the TSP and solving TSPTW[END_REF]. The Minimum Spanning Tree (MST) and even better the Minimum Spanning Arborescence (MSA) directly provide a lower bound to the TSP. In Assignment Problem (AP) relaxation, the solution can be composed of several disjointed cycles. With Held and Karp 1-tree relaxation, the solution is a Minimum Spanning Tree of G[V \ {1}] plus two edges connecting vertex 1 to this spanning tree.

The WeightedSubCircuits Constraint

The WeightedSubCircuits (WSC) constraint aims to generalize the Weight-edCircuit constraint. Instead of imposing a single Hamiltonian circuit on the whole graph, it enforces a Hamiltonian circuit for each subgraph induced by one or more subsets of vertices.

For the sake of simplicity, we assume that these subsets are defined by K + 1 set variables Set 1 ,...,Set K , Set dummy , the last subset being the set of discarded vertices. However, it is possible to adapt the definition with other representations of these subsets, for example with integer variables.

The WeightedSubCircuits constraint is intended to be combined with other constraints controlling the distribution of vertices in subsets Set 1 ,..., Set K , Set dummy which must form a partition of the set of vertices. The number K of subsets is an upper bound as some subsets may be empty. In addition, nonempty subsets must contain at least 2 vertices since the isolated vertices must belong to Set dummy .

Definition Definition 1. (WeightedSubCircuits)

Given a weighted graph G = (V, E, c), the constraint

WSC[G]([Set 1 , ..., Set K ], Set dummy , [N ext 1 , ..., N ext n ], [Cost 1 , ..., Cost K ], Z)
holds on the set variables Set 1 , ...Set K , Set dummy and the integer variables N ext 1 , . . . , N ext n , Z and Cost 1 , ..., Cost K if and only if:

1. the subsets Set 1 , . . . , Set K , Set dummy form a partition of V ; 2. ∀k ∈ 1..K, the set E k = {(i, N ext i ) | i ∈ Set k } defines a Hamiltonian circuit of G[Set k ] and (i,j)∈E k c(i, j) ≤ Cost k ; 3. ∀i ∈ V , i ∈ Set dummy ⇔ N ext i = i ; 4. K k=1 Cost k ≤ Z ;
This definition is illustrated by Figure 2. The set Set dummy contains all discarded vertices. As in Minizinc [START_REF] Nethercote | Minizinc: Towards a standard cp modelling language[END_REF] subcircuit constraint, we set N ext i = i for all discarded vertices. This allows constraint AllDifferent to be applied to all N ext i variables.

Because of the third rule, any subset Set k must be empty or contains at least 2 vertices. When K = 1, the constraint can be simplified since Set dummy = V \Set 1 and Z is an upper bound of Cost 1 . In the definition of the WeightedSubCircuits constraint we have assumed that the subsets are represented by set variables. This can facilitate the addition of external constraints on the subsets, such as a maximum cardinality to limit the number of vertices in each circuit. However, the constraint could also be defined with subsets represented by n membership integer variables {member i } i∈V . Moreover, the two representations can be combined thanks to channeling constraints ∀i ∈

1 Set1 = {1, 2, 6, 4} Set2 = {3, 5, 8} Set dummy = {7, 9} Cost1 = 10 Cost2 = 9 Z = 20 N ext1 = 2 N ext2 = 4 N ext3 = 8 N ext4 = 6 N ext5 = 3 N ext6 = 1 N ext7 = 7 N ext8 = 5 N ext9 = 9
V, ∀k ∈ 1..K, i ∈ Set k ⇔ member i = k and i ∈ Set dummy ⇔ member i = K + 1.
The WeightedSubCircuits constraint is clearly a generalization of the WeightedCircuit constraint:

WeightedCircuit[G](N ext 1 , ..., N ext n , Z) ≡ WSC[G]([V ], ∅, [N ext 1 , ..., N ext n ], [Z], Z)
Moreover, the WeightedSubCircuits constraint can also be used to implement some (but not all) variants of the generic Cycle constraint of CHIP [START_REF] Beldiceanu | Introducing global constraints in chip[END_REF]. For instance, one variant of the CHIP Cycle constraint holds for K cycles with p incompatible nodes (p ≤ K) that must belong to disjoint cycles with total cost constrained by two bounds. This cycle constraint is equivalent to a Weight-edSubCircuits constraint with additional unary constraints on the Cost k and Set k variables.

Since WeightedSubCircuits is a generalisation of WeightedCircuit, it is not surprising that filtering WeightedSubCircuits is NP-hard:

Decomposition

Before considering the development of specific propagators, we can try to decompose the WSC constraint into a set of standard constraints. Except for line 1.6, the WSC constraint can be decomposed into standard constraints as follows:

Proposition 1. WSC[G]( Set 1 , ...Set K , Set dummy , N ext 1 , ..., N ext n , Cost 1 , ..., Cost K , Z) ⇔ AllDifferent(N ext 1 , ..., N ext n ) (1.2) ∧ Partition(Set 1 , ..., Set K , Set dummy ) (1.3) ∧ ∀i ∈ V, i ∈ Set dummy ⇔ N ext i = i (1.4) ∧ ∀i ∈ V, ∀k = 1..K, i ∈ Set k ⇔ N ext i ∈ Set k (1.5) ∧ NoSubTours(Set 1 , ..., Set K , N ext 1 , ..., N ext n ) (1.6) ∧ ∀k = 1..K, i∈Set k c(i, N ext i ) ≤ Cost k (1.7) ∧ K k=1 Cost k ≤ Z (1.8)
The AllDifferent constraint on the N ext variables ensures that any vertex must belong to a cycle or must be isolated and then, thanks to line 1.4, must belong to Set dummy . We assume that the Partition constraints allows empty sets. Thanks to line 1.5 each cycle must be included in a single subset Set k .

The NoSubTours constraint enforces that such a cycle is an Hamiltonian cycle of the induced subgraph G[Set k ]. This is not a standard constraint but it is a generalization of the NoSubTour constraint [START_REF] Caseau | Solving small tsps with constraints[END_REF][START_REF] Pesant | An exact constraint logic programming algorithm for the traveling salesman problem with time windows[END_REF]. The next section will discuss NoSubTours filtering. The sum constraints (1.7) and (1.8) ensure that the cost of each cycle is greater or equal to the sum of the weights of its edges and that the total sum of Cost k variables is less or equal to Z.

Propagation

First we will look at the filtering of constraint NoSubTours in order to be able to implement constraint WeightedSubCircuits thanks to its decomposition. We will then propose a specific additional filtering for constraint Weighted-SubCircuits.

Since obtaining AC for these two constraints is NP-hard, the filtering algorithms that we will study in this section are necessarily incomplete.

NoSubTours

When N ext i is instantiated with j, the filtering rule 1.1 used for the constraint NoSubTour is dedicated to remove from the domain of N ext ε(j) any value leading to a cycle of size less that |V |.

For the NoSubTours constraints (1.6), the set {(i,

N ext i ), i ∈ Set k } must form a cycle of size |Set k | in G[Set k ].
Hence, if the path resulting from the instantiation N ext i = j has a length smaller than the size of the lower bound of Set k , this path cannot be closed at its ends to form a cycle. This corresponds to the following filtering rule:

N ext i = j ∧ i ∈ lb(Set k ) ∧ (L(β(i)) + L(j) + 1) < |lb(Set k )| -1 ⇒ N ext ε(j) = β(i) (1.9)
Conversely, if the resulting path passes through all vertices of the upper bound of Set k , the cycle must be closed and Set k is instantiated:

N ext i = j ∧ i ∈ lb(Set k ) ∧ (L(β(i)) + L(j) + 1) = |ub(Set k )| -1 ⇒ N ext ε(j) = β(i) ∧ Set k = ub(Set k ) (1.10)
NoSubTours filtering can also benefit from searching for connected components to ensure that lb(Set k ) is included in a connected (via N ext i variables) component of ub(Set k ).

Finally, we can notice that backtractable variables like β(i) can also be used to filter constraint (1.5) since all the vertices in the path passing through i and connecting β(i) to ε(i) must be in the same Set k than i. This corresponds to the following filtering rules:

i ∈ lb(Set k ) ⇒ {β(i), N ext β(i) , . . . , i, N ext i , . . . , ε(i)} ⊆ lb(Set k ) (1.11) and i ∈ ub(Set k ) ⇒ {β(i), N ext β(i) , . . . , i, N ext i , . . . , ε(i)} ∩ ub(Set k ) = ∅ (1.12)

WeightedSubCircuits

Previous works on the WeightedCircuit constraint have shown the benefit of dedicated filtering compared to separate filtering on the Circuit constraint and the cost of the circuit.

During the search, the vertices involved in the WeightedSubCircuits constraint can be divided in 4 categories (see Figure 3) :

A. The vertices in lb(Set dummy ) will not be part of the circuits. B. The vertices in lb(Set k ) will necessarily contribute to the value of Cost k and Z. C. The vertices in V \ (ub(Set dummy ) ∪ k lb(Set k )) cannot be excluded but

are not yet assigned to a Set k . They cannot yet contribute to the value of a specific Cost k but will necessarily contribute to the value of Z. D. For the vertices in ub(Set dummy ) \ lb(Set dummy ) it is still too early to know if they will be part of the circuits. Whether one considers a particular variable Cost k or the global variable Z, in both cases there is a subset of vertices that must be part of the solution and other vertices that may participate.

For instance, to find a lower bound for lb(Cost k ), the subset of required vertices is equal to lb(Set k ). It is unfortunate that it is not possible to consider only G[lb(Set k )] in order to find a lower bound for lb(Cost k ): To find a lower bound for Cost k , we must consider not only the mandatory vertices but also the potential vertices. This question can be reduced to the Steiner cycle problem, which is a generalization of the Steiner tree problem [START_REF] Hwang | The Steiner tree problem[END_REF].

Definition 2. (Steiner Cycle Problem

) Let H = (V, E, c) a weighted graph and V ⊆ V . The Steiner Cycle Problem SCP (H, V ) consists in finding an elementary cycle of minimum cost that contains all nodes in V (but may include additional vertices). The cost of an optimal solution will be noted OP T SCP (H, V ).

The TSP is a specific case of SCP where V = V .

Proposition 3. lb(Cost k ) ≥ OP T SCP (G[ub(Set k )], lb(Set k )) Proof. Cost k is the cost of a Hamiltonian cycle in G[Set k ].
Thus, this cycle must necessarily pass through all the vertices of lb(Set k ) and eventually through some vertices of ub(Set k ) \ lb(Set k ). This is the exact definition of

SCP (G[ub(Set k )], lb(Set k ))
Proposition 3 gives a way to filter Cost k . Since computing an optimal Steiner cycle is NP-hard, a lower bound can be determined by relaxing a constraint of SCP as is done for TSP. To do this, we start by defining an extended subgraph: Definition 3. (Extended subgraph) Given a weighted graph H = (V, E, c) and a subset V ⊆ V , the extended subgraph G(H, V ) is obtained by adding to H[V ] new edges (i, j), with weight c(i, j) = δ i,j , such that (i, j) ∈ E and there is a shortest path connecting i to j in H[(V \ V ) ∪ {i, j}] whose cost is equal to δ i,j . This definition is illustrated by Figure 5. The edges added to H[V ] correspond to a shortest path outside V and connecting two non-adjacent vertices of H[V ].

OP T SCP (H, V ) ≥ OP T T SP (G(H, V ))
Proof. Any Hamiltonian cycle C that is solution of SCP (H, V ) is composed of paths included in V and paths outside V . Let P i,j = i, x 1 , . . . , x t , j be a subpath of C such that i, j ∈ V and ∀p ∈ 1..t, x p ∈ V . If (i, j) ∈ E, the triangular inequality imposes that c(i, j) is not greater than the cost of P i,j . If (i, j) ∈ E, by construction of G(H, V ), there exists in G(H, V ) an edge (i, j) whose weight is lower or equal to the cost of P i,j . Thus, the cycle obtained by replacing in C all paths P i,j by edge (i, j) is a Hamiltonian cycle of G(H, V ) whose cost is lower or equal to that of C By combining propositions 3 and 4 we obtain a filtering rule for Cost k :

Corollary 1. lb(Cost k ) ≥ OP T T SP ( G(G[ub(Set k )], lb(Set k )) )
and therefore, a filtering rule for Z:

Corollary 2. lb(Z) ≥ K k=1 OP T T SP ( G(G[ub(Set k )], lb(Set k )) )
Since all Set k must be disjoined, all graphs G(G[ub(Set k )], lb(Set k )) are disjoined and so we have:

Proposition 5. lb(Z) ≥ OP T T SP ( K k=1 G(G[ub(Set k )], lb(Set k )) ) Computing ∪ K k=1 G(G[ub(Set k )], lb(Set k )) can be done in O(|V |(|E|+|V | log |V |
)) with at most |V \ ub(Set dummy )| calls to Dijkstra's algorithm. This is comparable to the complexity of some relaxation algorithms. For example, the Hungarian algorithm used for the Assignment Problem relaxation is in O(|V | 3 ).

Thanks to Proposition 5, a lower bound of Z can be computed with a relaxation of the TSP, as in the case of constraint WeightedCircuit.

This bound is directly related to the state of variables Set k , which define the vertices of the extended subgraphs, and to the domains of variables N ext i , which fix adjacency in G. Depending on the relaxation used, it is also possible to take into account variable Set dummy .

For example, suppose we use the relaxation corresponding to the Assignment Problem (AP). For any graph H, a solution of AP (H) is a set of disjoined minimum cost elementary circuits covering all the vertices of H. Applying AP to extended subgraphs results in a set of sub-cycles covering all type B vertices of Figure 3. However, type C vertices are not covered by these sub-cycles even though they will necessarily be part of the final cycles. To take into account these vertices we can expand the extended subgraphs to vertices of type C.

Let Since G * is built from a subgraph that contains the C-type vertices, we have a new lower bound for Z:

Proposition 6. lb(Z) ≥ OP T AP (G * ) (1.13)
The proof is similar to that of Proposition 4. For the graph in Figure 6, the cycle set { 1, 2, 3, 4, 1 , 8, 11, 8 , 9, 10, 9 } is an optimal solution to AP (G * ). The cost (33) of this solution is a lower bound of Z, whatever the vertices added to Set 1 or Set 2 . Moreover, according to the upper bound of Z, some edges can be discarded because they cannot be part of a solution. This filtering is based on computing a reduced cost for each arc (i, j) not in the solution of AP (G * ), i.e., the minimum increase of the overall cost for setting N ext i to j (see [START_REF] Benchimol | Improved filtering for weighted circuit constraints[END_REF][START_REF] Ducomman | Alternative filtering for the weighted circuit constraint: Comparing lower bounds for the TSP and solving TSPTW[END_REF]). For instance, with ub(Z) = 40, edges [START_REF] Focacci | A hybrid exact algorithm for the TSPTW[END_REF][START_REF] Hwang | The Steiner tree problem[END_REF] and [START_REF] Francis | Explaining circuit propagation[END_REF][START_REF] Kaya | A filter for the circuit constraint[END_REF] could be eliminated. This filtering concerns only the edges of G * that belong to G.

Experimental Results

This section presents some preliminary results to evaluate the benefits of the constraint WeightedSubCircuits. These preliminary experiments aim to measure the interest of a filtering based on Steiner cycles. Rather than generating random data we consider the Balancing Bike Sharing Systems (BBSS). This problem is linked to the management of a shared bicycle fleet. The objective is to optimize a tour of the stations in order to remove bicycles from overfilled stations and refill empty stations. The capacity of the transport vehicle and the time available do not allow all stations to be optimized. We implemented the CSP model of [START_REF] Gaspero | Constraint-based approaches for balancing bike sharing systems[END_REF][START_REF] Gaspero | Balancing bike sharing systems with constraint programming[END_REF] which uses a Cycle constraint. We simply modified it in order to make dummy vertices appear: to ensure that some stations will not be visited, we imposed that the demand for each visited station be fully satisfied rather than partially handle all stations. The benchmark is based on instances from the city of Vienna given by [START_REF] Gaspero | Constraint-based approaches for balancing bike sharing systems[END_REF]. To gerenate additional instances from size 12 to 18, we extracted a subset of vertices from instances with 20 vertices. Unlike the initial article which was based on a Large Neighborhood Search (LNS) approach, we used a standard search procedure used with fixed ordering of variables. This limits the size of instances that can be processed.

We compared 4 models based on:

a simple Cycle constraint using the NoSubTour filtering.

the decomposition of the WeightedSubCircuits constraint presented in section 5.1, with the filtering rules 1.9 to 1.12 for the NoSubTours constraint the NoSubTours constraint plus the filtering rule for Z based on AP (G * ) (Proposition 6) the previous filtering rules with additional filtering on the N ext i variables using reduced costs from AP (G * )

We implemented these models in the Java library Choco 4 [START_REF] Prud'homme | Choco Documentation. TASC, IN-RIA Rennes[END_REF]. All the experiments were executed on a Linux machine with Intel(R) Xeon(R) CPU E5-2680 (2.40 GHz). The time limit for each run was set to 2 hours.

Table 1 summarizes the results obtained for series of 30 graphs of different sizes. When all the graphs in a series have been resolved, the CPU time and the number of nodes are an average over the 30 graphs. Otherwise, only the number of resolved instances is displayed. These preliminary results show that the model based on the decomposition of the WeightedSubCircuits constraint allows to find an optimal solution for instances up to 20 vertices while the model based on the Circuit constraint of Choco (NoSubTour) reaches the time limit for several small instances. In addition, the filtering of the Z variable based on the AP (G * ) relaxation seems to be quite effective. The last columns show that the computation of G * is even more profitable if it is used to eliminate edges by filtering the N ext i variables.

Conclusion

In this paper, we considered circuit constraints that allow the modeling of tour problems in a CP solver. We have proposed a new global constraint, named WeightedSubCircuits, that enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph. The constraint is posted on a family of subsets of vertices to obtain a Hamiltonian circuit in each subgraph induced by a subset. The WeightedSubCircuits constraint is intended to be combined with other constraints that control the composition of these subsets and the dummy set of discarded vertices.

We have shown that the WeightedSubCircuits constraint can improve filtering where the WeightedCircuit constraint cannot be used because of the dummy vertices. We have proposed an adaptation of the NoSubTour constraint filtering that is compatible with discarded vertices. We have shown that computing a lower bound of the cost of each circuit can be reduced to a Steiner circuit problem. We demonstrated how to obtain a lower bound of the Steiner circuit by solving a TSP relaxation on an extended subgraph. To obtain a lower bound of the total cost of all circuits, we have shown that it is possible to take into account the required vertices that are not yet assigned to a subset, using AP relaxation. Preliminary experiments have shown the potential of this approach and encourage further exploration of filtering rules for the new constraint.

Fig. 2 .

 2 Fig. 2. An example of a weighted graph and a set of variables for which the constraint WSC[G]([Set1, Set2], Set dummy , [N ext1, ..., N ext9], [Cost1, Cost2], Z) holds.

Theorem 1 .

 1 Achieving Bounds Consistency (BC) on WSC is NP-hard. Proof. Deciding if a graph G = (V, E, c) has a Hamiltonian circuit of cost less or equal to a given value p is NP-complete. Consider the constraint WSC[G]([Set 1 ], Set dummy , [N ext 1 , ..., N ext n ], [Cost 1 ], Z) where lb(Set 1 ) = V and for each variable N ext i , dom(N ext i ) = {j | (i, j) ∈ E} and D(Cost 1 ) = D(Z) = {0, ..., p}. BC empties the domain of Z if and only if G does not admit a Hamiltonian circuit of cost less or equal than p

Fig. 3 .

 3 Fig. 3. Vertex distribution for constraint WeightedSubCircuits during the search: A vertices are definitely discarted and inserted in subset Set dummy ; B vertices are definitely added to one subset Set k ; C vertices can no longer be discarded but are not yet assigned to any subset S k ; D vertices can belong to any subset.

Proposition 2 .Fig. 4 .

 24 Fig. 4. The optimal value for T SP (G[lb(Set k )]) is equal to 24 whereas OP TT SP (G[lb(Set k ) ∪ {5, 6}]) is equal to 21.

Fig. 5 .Proposition 4 .

 54 Fig. 5. Extended subgraph G(H, V ) for a graph H = (V, E, c) and a subset V ⊆ V

  S B = K k=1 lb(Set k ) the set of type B vertices and S C the set of type C vertices. We have S C = V \ (ub(Set dummy ) ∪ S B ). We define the global extended subgraph G * as follow: Definition 4. (Global extended subgraph) The global extended subgraph G * is an extended subgraph built on G[S B ∪ S C ] by adding only edges between two vertices of the same lb(Set k ) or between a vertex of S B and a vertex of S C . This definition is illustrated by Figure 6. Computing G * has the same complexity O(|V |(|E| + |V | log |V |)) as computing all extended subgraphs.

Fig. 6 .

 6 Fig. 6. En example of global extended subgraph G * , with SC = {4} and SB = lb(Set1) ∪ lb(Set2) = {1, 2, 3, 8, 9, 10, 11} and N ext1 = 2, N ext2 = 3

Table 1 .

 1 Average results on BBS instances for the WeightedSubCircuits.

		Circuit Decomposition of	WSC filtering on Z with	WSC filtering on
			WSC		AP (G * ) relaxation	Z and N exti
	|V | # solved time (sec) nodes time (sec)	nodes	time (sec) nodes
	10 12/30	13	201,658	6	78,735	6	66,984
	12 6/30	89	1,415,712	16	228,809	12	159,703
	14		381	6,035,049	49	723,136	40	522,914
	16 18	0/30	1515	23,729,425 26/30	181 526	2,480,824 6,480,702	121 369	1,489,637 4,017,667
	20			19/30	1523	16,147,092	1097	10,475,711

Acknowledgement This work has been realized with the support of the High Performance Computing Platform HPC@LR, financed by the Languedoc-Roussillon -Midi-Pyrenees Region, Montpellier Mediterranean Metropole and the University of Montpellier.


Assoul Abdelkarim
email: assoulabdelkarim1@gmail.com

The sum of the natural numbers peers, odd of p th degree.

By: Assoul Abdelkarim

Professor of Secondary Education

In number theory, the sums of the natural numbers from 1 degree up to p th degree are known:

1+2+3+…. +n = n (n+1) 1 2 +2 2 +3 2 +…. +n [START_REF] Weisstein | CRC Concise Encyclopedia of Mathematics[END_REF] The purpose of article is to find a general formula new which permit to calculate the sums of natural numbers peers and odd of p th degree, using the formula of the binomial of Newton,the formula of Faulhaber as well as numbers of Bernoulli - ----------------------------------------------------------(1) Formula Faulhaber

(2) We take the Bernoulli numberB 1 =+ 1. The sum of the natural numbers peers of p th degree.

The sum of the natural numbers peers.

For any natural number n, we have:

Proof:

For any natural number n, we have:

2 = n (n+1) 1.2
The sum of the natural numbers peers of 2 nd degree.

For any natural number n, we have:

2 2 +4 2 +6 2 +……+ (2n) 2 = n (n+1) (2n+1) Proof:
For any natural number n, we have:

n (n+1) (2n+1) = n (n+1) (2n+1)
1.3 The sum of the natural numbers peers of 3 th degree.

For any natural number n, we have:

2 3 +4 3 +…. + (2i) 3 =2n 2 (n+1) 2
Proof:

For any natural number n, we have:

8 3 = 8× n 2 (n+1) 2 = 2 n 2 (n+1) 2

2+4+6+…..+2n = n (n+1)

In the same way, we found:

n (6n 4 +15n 3 +10n 2 -1) n 2 (2n 4 +6n 3 +5n 2 -1)

1.4

The sum of the natural numbers peers of p th degree.

Formula. For any natural number n, we have:

B j n p+1-j
où pЄΝ, p<n et B j the numbers of Bernoulli.

Proof:

It can be easily seen that for any integer n, it was:

p p
We apply the formula of de Faulhaber, there is:

B j n p+1-j

Example: For any natural number n, we have:

1)

1+3+5+…..+ (2n+1) = (n+1) 2
Proof: for any natural number n, we have:

+ (n+1) = n (n+1) + (n+1) = (n+1)(n+1) = (n+1) 2 2.2
The sum of the natural numbers odd of nd degree.

For any natural number n, we have: For any natural number n, we have:

2 = 4 = n (n+1) (2n+1) + 2n (n+1) + (n+1) = (n+1) [ n (2n+1) + 2n+1] = (n+1) (2n+1) ( n+1) = (n+1) (2n+1) (2n+3)
For any natural number n, we have:

2 . 2 . 1

 221 3 + n 2 + n] = (2n 3 +3n 2 +n) = n (2n 2 +3n+1) = n (n+1) (2n+1) The sum of the natural numbers odd of p th degree. The sums of the natural numbers odd.

2.4The sum of the natural numbers odd of p th degree. Formula. For any natural number n, we have:


Luciana Arantes

Evripidis Bampis

Alexander Kononov

Manthos Letsios

Giorgio Lucarelli

Pierre Sens

Scheduling under Uncertainty: A Query-based Approach

We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic errorquery scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the online versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.

Introduction

Scheduling problems under uncertainty have been studied in different contexts such as on-line optimization, robust optimization, and stochastic optimization. A common assumption in all these models is that the uncertain information cannot be known before the construction of the schedule. However, in some applications it is possible to know the exact input information at some extra cost [START_REF] Erlebach | Query-competitive algorithms for computing with uncertainty[END_REF]. In this paper, we consider scheduling with faults/errors and we introduce a new non-probabilistic model with explorable (query-able) uncertainty. Each unit-time error is characterized by an uncertainty area during which the error will occur, and it is possible to learn the exact slot at which it will appear by issuing a query operation of unit cost. Our goal is to reveal enough error-free slots by querying the smallest number of errors in order to be able to successfully execute n unit-time jobs. Note that a query can be seen as an unsuccessful attempt of execution. In Figure 1 (left), we give a simple instance with 6 errors: error e 1 with uncertainty area (0, 4], error e 2 with (0, 2], and so on.

More formally, assume that the time-line is split into unitsize slots. For simplicity, we refer to the slot (t -1, t], for any t ≥ 1, by its right limit, i.e., t. We are given a single machine, n unit-time jobs and a set E of k unit-time errors. The execution of each job takes place into a single slot. Each error e ∈ E is associated with an uncertainty area A e = (s e , f e ] and its actual slot of appearance t * e ∈ (s e , f e ]. We assume that, for any two errors e, e ∈ E, it holds that t * e = t * e . A slot t is called error-free if for each error e ∈ E where t ⊆ A e it holds that t = t * e . In order to reveal an error-free slot we need to query all errors whose uncertainty area includes it. We propose to study the following two problems: (i) The error-query scheduling problem: Find n error-free slots by performing the minimum number of queries; (ii) The lexicographic errorquery scheduling problem: Find the earliest n error-free slots by performing the minimum number of queries.

We consider two versions of the above problems. In the off-line version the whole instance and its characteristics are known in advance. In the on-line version the set of errors and their uncertainty areas are known to the algorithm, but the adversary can decide in an on-line way the slot of appearance t * e for each e ∈ E. In other words, there is an iterative game between the on-line algorithm which queries an error and the adversary which reveals the slot of appearance of this error, and so on. Even-though the off-line version seems of marginal interest, it can be used as a lower bound on the number of queries for the on-line case. As a measure of efficiency for the on-line problems we use the competitive ratio. An algorithm is ρ-competitive if it makes at most ρ times the optimum number of queries for any instance of the problem.

In what follows, we define two special families of instances concerning the uncertainty areas of the errors. Both families are widely studied in scheduling and graph theory literature. Agreeable instances: A set of uncertainty areas is agreeable, if for any two errors e and e with s e ≤ s e , it holds that f e ≤ f e . In other words, there is a unique ordering of the uncertainty areas of the errors with respect to both their left and their right limits, i.e., if s e1 ≤ s e2 . . . ≤ s e k then f e1 ≤ f e2 . . . ≤ f e k . Note that agreeable instances correspond to proper interval graphs. Laminar instances: A set of uncertainty areas is laminar, if for any two errors e and e with s e ≤ s e , it holds that either f e ≤ s e or f e ≥ f e . The laminar instances have a tree-like structure and they can be represented as a forest. In order to see such a structure, consider the following construction. Each error e , 1 ≤ ≤ k, is assigned to a node v . For any two nodes v and v with A e ⊂ A e , an edge connects them if there is no other error e such that A e ⊂ A e ⊂ A e . In the case of multiple errors with the same uncertainty area, we consider an arbitrary order of them and edges between nodes of any two consecutive errors are added to the tree based on this order. Note that the trees created by this construction are considered to be rooted. Specifically, the root of each tree is the node that corresponds to its error with the largest uncertainty area. Moreover, there is an order among the children of a given node which is determined by the order of the uncertainty areas of the corresponding errors in the time-line. An example of a laminar instance along with its tree representation can be seen at Figure 1.

Related work:

The work in the area of explorable uncertainty has been initiated in the seminal paper of Kahan [Kahan, ] for selection problems. Since then, a series of papers study many other problems in this context: finding the k-th smallest value in a set of uncertainty intervals [Feder et al., 2003;Gupta et al., 2011;[START_REF] Kahan | A model for data in motion[END_REF], caching problems in distributed databases [Olston and Widom, ], the shortest path problem [Feder et al., 2007], the knapsack problem [Goerigk et al., 2015], the minimum spanning tree problem [START_REF] Hoffmann | Computing minimum spanning trees with uncertainty[END_REF][START_REF] Megow | [END_REF]. In most of these works the aim is to minimize the number of queries to guarantee an exact optimum solution, while some other study the trade-off between the number of queries and the precision of the returned solution [Olston and Widom, ]. Recently, explorable uncertainty has been introduced in scheduling [Dürr et al., ]. The uncertain information concerns the processing time of each job for which an upper bound is known in advance. It is possible to learn the exact processing time by testing at the price of a unit cost. This line of research has similarities with models that have been extensively studied in AI for computation decision support [START_REF] Boutilier | [END_REF], especially with models treating adaptive preference elicitation to combinatorial domains [START_REF] Benabbou | Incremental weight elicitation for multiobjective state space search[END_REF]a;[START_REF] Drummond | Elicitation and approximately stable matching with partial preferences[END_REF]Gelain et al., 2010].

However, our model is also related to search theory [Angelopoulos, 2016]. For instance, consider an environment where the search domain is modeled by a star, i.e., consists of a set of rays which have a common intersection point, and there are more than one targets. The goal of the searcher is to locate some of these targets by adopting the expanding search paradigm in which the cost of re-exploration is negligible [START_REF] Alpern | Steve Alpern and Thomas Lidbetter. Mining coal or finding terrorists: The expanding search paradigm[END_REF]. It is not difficult to see that the instance of Figure 2 can be interpreted as a star with b rays and one target (corresponding to one error-free slot) in every ray. The goal is to find some among these targets, while a query corresponds to the exploration of a ray by an additional unit of distance. It has to be pointed out here that star search offers an abstraction for modeling different applications such as interruptible algorithms [Angelopoulos, ], or database query optimization [Condon et al., 2009].

Our contribution: We first give an optimal polynomialtime algorithm for the off-line error-query scheduling problem. For the on-line version of the problem, we prove that the competitive ratio of any on-line algorithm is Ω( √ k) even if the instance is laminar and agreeable and even if we search for only one free slot. Then, we propose a O( √ k)-competitive algorithm for laminar instances. Finally, in Section 4, we deal with the lexicographic error-query scheduling problem by matching lower and upper bounds of the competitive ratio for the on-line version. The elementary interval is an important concept in most of our proofs because of the following property: Property 1. Given an elementary interval I i , all errors in E(I i ) must be queried in order to reveal an error-free slot during I i . Moreover, if all errors in E(I i ) are queried then all error-free slots of the set F (E(I i )) are revealed.

Based on the above property, it is meaningless to ask fewer than |E(I i )| errors of E(I i ) when targeting some error-free slots of I i . Moreover, there is no reason for not using all error-free slots in F (E(I i )) when all errors in E(I i ) are already queried, unless there is not a sufficient number of unscheduled jobs. Therefore, a set of elementary intervals is also sufficient to represent a solution to our problem. More specifically, given a set of elementary intervals, we need to query all errors whose uncertainty area intersects them. If the number of error-free slots that are revealed is greater than n, then we select arbitrarily n of them in the case of the errorquery scheduling problem, or the earliest n of them in the case of the lexicographic error-query scheduling problem.

Finally, we give some additional notation regarding the laminar instances. Given a vertex v of depth d (i.e., the distance in hops from v to the root of its tree is equal to d ), we define the level of the error e to be equal to d +1. Moreover, for any node v in the tree-like representation of a laminar instance, let T (v ) be the subtree rooted at v . For any (sub)tree T , let E(T ) be the set of errors corresponding to the nodes of T . Due to the laminar structure, an algorithm does not have any interest to query an error e if it has not already queried all errors corresponding to the nodes in the path from v to the root. Given a set E of already queried errors which follows this observation, we say that a subtree T (v ) is maximal with respect to E if e ∈ E and either v has no ancestors or the errors corresponding to all ancestors of v are in E . For example, for the instance depicted in Figure 1, if E = {e 4 } then the subtrees T (v 1 ) and T (v 5 ) are maximal.

The Error-query Scheduling Problem

In this section, we firstly present a polynomial-time algorithm for the off-line version of the error-query scheduling problem. Then, we consider the on-line version of the problem and we present a lower bound to the competitive ratio as well as a O( √ k)-competitive algorithm for laminar instances.

A Polynomial-time Algorithm

We present here a polynomial-time algorithm for finding an optimal off-line solution for the error-query scheduling problem. The proposed algorithm uses the representation of a solution to the problem by just indicating a set of elementary intervals, as this is implied by Property 1 and it is explained in preliminaries. Such a representation can be also used for partial solutions, i.e., solutions that reveal less than n errorfree slots. Moreover, each (partial) solution S corresponds to a triplet (i, j, ), where i is the index of the latest elementary interval used, j is the number of error-free slots that are revealed and is the number of errors that are queried. Note that a triplet (i, j, ) may correspond to more than one solutions. By slightly abusing the notation, we denote by E(S) the set of errors that are queried by the solution S.

Our algorithm keeps a set of partial solutions and it iterates on the elementary intervals: at iteration i, 1 ≤ i ≤ |I|, the elementary interval I i is considered. Let S i-1 be the set of partial solutions at the end of the iteration i -1. We extend each S ∈ S i-1 to the partial solution S by including to it the elementary interval I i and we add both S and S to S i : if S corresponds to the triplet (i , j,

) with i ≤ i -1, then S = S ∪{I i } corresponds to the triplet (i, j +|F (E(I i ))|, |E(S)∪ E(I i )|), where ≤ |E(S) ∪ E(I i )| ≤ + |E(I i )|.
Note that several partial solutions can be dominated by others. We say that a partial solution S 1 corresponding to (i 1 , j 1 , 1 ) is dominated by the partial solution S 2 corresponding to (i 2 , j 2 , 2 ) if i 1 ≤ i 2 , j 1 ≤ j 2 and 1 ≥ 2 . At the end of the iteration i we eliminate all dominated partial solutions from S i . Observe that this elimination phase removes also all but one partial solutions that correspond to the same triplet (i, j, ).

A formal description of the algorithm is given below.

Algorithm 1

1: Initialization: S ← ∅ (which corresponds to (0, 0, 0)), S0 ← {S}, A ← Ii 2: for i = 1 to |I| do 3: Si ← Si-1 4:
for each S ∈ Si-1 corresponding to (i , j, ) do 5:

Create a new partial solution S ← S ∪ {Ii} corresponding to

(i, j + |F (E(Ii))|, |E(S) ∪ E(Ii)|) 6: if |F (E(S ))| ≥ n and |E(S )| < |E(A)| then 7: A ← S 8: else if |F (E(S ))| < n then 9:
Si ← Si ∪ {S } 10:

for each pair S1, S2 ∈ Si where S1 corresponds to (i1, j1, 1) and S2 corresponds to (i2, j2, 2) do 11:

if i1 ≤ i2 and j1 ≤ j2 and 1 ≥ 2 then 12:

Si ← Si \ {S1} 13: return A Theorem 1. Algorithm 1 finds an optimal solution for the offline error-query scheduling problem in time polynomial in k.

Proof. Note that, if we remove the elimination step in Lines 10-12 of the algorithm, then it will create all possible solutions, i.e., all possible combinations of elementary intervals. Hence, in order to prove the correctness of our algorithm, it is sufficient to show that the elimination step does not remove any partial solution which can lead to a better final solution.

For the sake of contradiction, assume that a partial solution S 1 corresponding to (i 1 , j 1 , 1 ) is eliminated by the algorithm due to its domination by the partial solution S 2 corresponding to (i 2 , j 2 , 2 ) in iteration i. Moreover, let I 1 be the set of elementary intervals that can be added to S 1 and get the final solution S 1 ∪ I 1 which queries strictly less errors than the solution obtained by the algorithm. Note that the solution S 1 ∪I 1 reveals j 1 +|F (E(I 1 ))| error-free slots. Consider now the solution S 2 ∪ I 1 which reveals j 2 + |F (E(I 1 ))| error-free slots. By the definition of the elimination rules we have that j 1 ≤ j 2 , and hence S 2 ∪ I 1 reveals at least as many error-free slots as S 1 ∪ I 1 . For the errors that are queried by

S 1 ∪ I 1 we have that |E(S 1 ∪ I 1 )| = |E(S 1 ) ∪ E(I 1 )| = |E(S 1 )| + |E(I i )|-|E(S 1 )∩E(I 1 )| = 1 +|E(I i )|-|E(S 1 )∩E(I 1 )|. Similarly, for S 2 ∪ I 1 it holds that |E(S 2 ∪ I 1 )| = 2 + |E(I i )| -|E(S 2 ) ∩ E(I 1 )|. Since i 1 ≤ i 2 , we have that |E(S 1 ) ∩ E(I 1 )| ≤ |E(S 2 ) ∩ E(I 1 )|.
By taking into account the elimination rule 1 ≥ 2 , we have that |E(S 1 ∪ I 1 )| ≥ |E(S 2 ∪ I 1 )|, which is a contradiction to the assumption that S 1 ∪ I 1 queries strictly less errors than the solution obtained by the algorithm.

For the complexity of the algorithm, note first that it iterates O(|I|) = O(k) times. By the definition of the elimination rules, in each iteration we keep only one value of j for each pair of i and . Thus, the parameter j can take at most min{n, k 2 } different values. Therefore, the number of partial solutions in each iteration is at most min{n, k 2 } × k × |I| < k 4 . Finally, the elimination step considers all pairs of partial solutions, whose number is polynomial to k, and hence the theorem follows.

A Lower Bound for the On-line Problem

We next consider the on-line version of the error-query scheduling problem. Recall that we assume that the errors and their uncertainty areas are known to the on-line algorithm, but not their slots of appearance.

In this section we present a lower bound to the competitive ratio of any on-line algorithm. Note that this lower bound is valid for particularly simple instances, i.e., there is only one job to execute as well as the uncertainty areas of the errors belong in both laminar and agreeable families of instances. Theorem 2. The competitive ratio of any on-line algorithm for the error-query scheduling problem is Ω( √ k), even in the case where n = 1 and the instance is both laminar and agreeable.

Proof. Consider the instance shown in Figure 2 which consists of k = b 2 errors. The errors are partitioned into b groups, E 1 , E 2 , . . . , E b , each one containing b errors. The uncertainty area of the error e ,i , i.e., the i-th error in E , spans into the interval (( -1)(b + 1) + i -1, (b + 1)], where 1 ≤ i ≤ b and 1 ≤ ≤ b. The uncertainty areas of any two errors belonging in different groups do not intersect. Specifically, in the interval (( -1)(b+1), (b+1)], 1 ≤ ≤ b, there exist only the uncertainty areas of the b errors of E . Since this interval spans into b + 1 slots, there is a unique error-free slot available in it. The goal is to find one error-free slot in the whole instance in order to execute one job. Note that the constructed instance is both laminar and agreeable. Given the above instance, we claim that any on-line algorithm can be forced by the adversary to query at least b errors, while the optimal solution will query only one. According to Property 1 there is no reason to query error e ,i without also querying all errors in {e ,1 , . . . , e ,i-1 }. In particular, if the error-free slot of the set E appears in position (b + 1), then any algorithm must query all errors in {e ,1 , . . . , e ,b } in order to reveal it. On the other hand, if the error-free slot appears in position ( -1)(b + 1) + 1 one request is sufficient to find it.

Assume now that an on-line algorithm has queried any b-1 errors. We say that E is unimpaired if the on-line algorithm queries no errors from this group. Let us denote the set of unimpaired groups by E 0 and let E 1 = {E 1 , E 2 , . . . , E b } \ E 0 . We note that both sets are non-empty and each group E i contains at least one not updated error.

If E ∈ E 1 the adversary sets the unique error-free slot in the position (b+1). Otherwise, the adversary sets the unique error-free slot in the position ( -1)(b + 1) + 1. It follows that the on-line algorithm find no error-free slot after b -1 queries and must update at least one more error. In its turn, the optimal solution asks the error e l,1 for E ∈ E 0 and reveal the error-free slot ( -1)(b + 1) + 1.

Concluding, the adversary can work in such a way that forces the on-line algorithm to query at least b errors, while the constructed instance contains an error-free slot that can be revealed by only one query. By recalling that b = √ k, the theorem follows.

An O( √ k)-competitive Algorithm for Laminar Instances

In this section we give an O( √ k)-competitive algorithm for laminar instances that exploits their tree-like structure. In each iteration, the algorithm updates the set of already queried errors E and considers the set of all maximal subtrees with respect to E as these are defined at the end of Section 2. We say that the subtree T (v ) is big if it contains more than √ k nodes, that is the uncertainty area of e includes the uncertainty areas of more than √ k errors. Otherwise, we say that T (v ) is small. For simplicity, we call also big and small the errors corresponding to the root of big and small subtrees, respectively. Then, given a set of maximal subtrees, our algorithm at each iteration queries the following errors. For each big maximal subtree T (v ) the error e is queried. Moreover, the algorithm queries the errors corresponding to all nodes of the small maximal subtree that contains the maximum number of error-free slots. Note that the number of error-free slots in a maximal subtree can be easily computed. Algorithm 2 presents a formal description of the procedure.

Theorem 3. Algorithm 2 is O( √ k)
-competitive for the errorquery scheduling problem on laminar instances.

Proof. A big subtree cannot be part of a small subtree, that is if v is the parent of v and T (v ) is big, then T (v ) is also big. Based on this, we observe that the algorithm at iteration i considers all big subtrees of level i. Since these subtrees are node-independent and each of them contains more than √ k errors, their number cannot be greater than √ k. Hence, the algorithm handles at most √ k big subtrees per iteration in Lines 5-10, and for each subtree it queries only one error. Moreover, by the definition of small subtrees, the algorithm queries at most √ k errors in Line 12. Therefore, at each iteration the algorithm queries at most 2 √ k errors.

Algorithm 2

1: i ← 0; E ← ∅ 2: S0: the set of trees in the forest representation of the initial instance (the initial set of maximal subtrees) 3: while n > 0 do 4:

i ← i + 1; Si ← Si-1 5:

for each big subtree T (v ) ∈ Si-1 do 6:

Query the error e and set E ← E ∪ {e } 7:

Reduce n by the number of the error-free slots that are revealed due to the query of e 8:

Si ← Si \ {T (v )} 9:

for each children v of v do 10:

Si ← Si ∪ {T (v )} 11:

Let T i ∈ Si-1 be the small maximal subtree that can reveal the maximum number of error-free slots 12:

Query all errors in E(T i ) and set

E ← E ∪ E(T i ) 13: Si ← Si \ {T i } 14:
Reduce n by the number of the error-free slots that are revealed due to the query of the errors in E(T i ) 15: return E In order to finish the proof, we need to show the following claim: the error-free slots revealed by the algorithm up to the end of iteration i, are at least equal to the error-free slots revealed by any solution after querying exactly i errors. This claim can be rephrased as: if the algorithm performs i * iterations in total then the optimal solution should query at least i * errors, and hence the competitive ratio is at most

2 √ k•i * i * = O( √ k).
In order to prove the claim, consider a solution of any algorithm A that has queried i errors. Let i big and i small be the number of the big and the small errors, respectively, in this solution, i.e., i = i big + i small . As mentioned above, there is no interest to query an error without previously querying its parent in the forest representation, since the instance is laminar. Hence, all i errors queried by A are of level at most i. Then, all i big big errors queried by A are also queried by our algorithm, since the later one has queried all big errors of levels 1, 2, . . . , i at the end of iteration i. Thus, it remains to show that the i small errors queried by A cannot reveal more error-free slots than the errors in T 1 ∪T 2 ∪. . .∪T i queried by our algorithm. This is true, since i small ≤ i and these i small subtrees are selected by our algorithm in order to contain the maximum number of error-free slots.

The Lexicographic Error-query Scheduling Problem

In this section we consider the lexicographic variant of our problem in which we need to query the minimum number of errors such that to reveal the n earliest error-free slots. The off-line case for this problem is trivial, since the algorithm knows the slot of appearance of each error, and hence the n earliest error-free slots. Thus, it suffices to query all errors whose uncertainty areas contain these slots. In the following, we deal only with the on-line case. We first present a lower bound which holds also for agreeable instances, and then we propose a competitive algorithm for general instances which matches asymptotically this lower bound.

Note that the lexicographic error-query scheduling problem is easy for laminar instances and an optimal on-line algorithm can be designed. This algorithm is based on maximal subtrees and the fact that the number of error-free slots in a maximal subtree can be immediately calculated. Indeed, given the set E of the already queried errors and a maximal subtree T (v ) with respect to E , the number of error-free slots in (s e , f e ] is equal to

(f e -s e ) -|E(T (v ))| -a(E , T (v ))
where E(T (v )) is the set of errors corresponding to the nodes of T (v ) and a(E , T (v )) is the number of errors in E whose appearance slot is in (s e , f e ]. Then, the algorithm for laminar instances queries at each iteration the error that corresponds to the root of the leftmost maximal subtree which contains at least one error-free slot. This procedure terminates when the n earliest error-free slots are revealed. The optimality of the algorithm comes from the fact that the queried errors reveal the n earliest error-free slots, while the algorithm queries an error only if it can reveal at least one of these error-free slots. Theorem 4. There is an optimal on-line algorithm for the lexicographic error-query scheduling problem on laminar instances.

A Lower Bound

We present here a lower bound to the competitive ratio of any on-line algorithm. This lower bound is valid for instances where there is only one job to execute, one error-free slot available as well as the uncertainty areas of the errors form an agreeable instance. Note that the lexicographic property is implied by the uniqueness of the error-free slot. Theorem 5. The competitive ratio of any on-line algorithm for the lexicographic error-query scheduling problem is Ω(log 2 k), even if n = 1 and the instance is agreeable.

Proof. We consider the instance shown in Figure 3 which spans into the time interval (0, k + 1]. In this instance there are k errors, while the uncertainty area of the error e spans in ( -1, + 1]. Note that there exists exactly one errorfree slot in this instance which should be found by the on-line algorithm in order to execute the n = 1 job. Consider any on-line algorithm A and assume that it initially queries the error e . The adversary has two choices: the slot of appearance of e is set to be either ( -1, ] or ( , +1]. In the first case A immediately learns that the error-free slot cannot be in the interval (0, ]. Indeed, there are -1 errors whose uncertainty area entirely spans in this interval plus e whose appearance slot is ( -1, ]. Hence, there are errors whose appearance slots are in (0, ]. Due to the assumption that two errors cannot have the same uncertainty slot, we conclude that there is not an error-free slot in (0, ]. In a similar way, if the adversary sets the slot of appearance of e to be ( , + 1] then A immediately learns that the error-free slot cannot be in the interval ( , k + 1]. In both above cases, the algorithm A can eliminate a part of the instance and continue the search for the error-free slot by querying a new error to the other part. We assume that A is a reasonable algorithm in the sense that it does not query errors for which it is easy to verify that cannot reveal any error-free slot. Note that the subinstance in which A will continue its search, has exactly the same form as the initial instance, but it has a smaller spanning interval and less errors.

0 1 2 3 4 -2 -1 + 1 + 2 k -3 k -2 k -1 k k + 1 . . .
Based on the above observation, we consider that the adversary applies always the following policy: given a subinstance that spans in the interval ( 1 , 2 + 1] and the query for an error e , where 1 ≤ ≤ 2 , set t * e = ( -1, ] if -1 ≤ 2 + 1 -, and t * e = ( , + 1] otherwise. In this way, the spanning interval of the remaining sub-instance which will be considered by the reasonable algorithm A is maximized. Specifically, the new sub-instance spans to an interval of size max{ -1 , 2 + 1 -} and it contains max{ -1 , 2 + 1 -} -1 errors. On the other hand, the algorithm A should select the error e such that the new sub-instance is of minimum size, which can be achieved if = 2-1

2

. In other words, at each step the spanning interval of the sub-instance is decreased by half, and hence A is forced to query O(log 2 k) errors before revealing the errorfree slot. Since all slots are included in the uncertainty area of at most two errors, the adversary needs at most two queries to reveal the error-free slot, and the theorem follows.

An O(log 2 k)-competitive Algorithm

In this section we propose an on-line algorithm for the lexicographic error-query scheduling problem whose main idea is to do a pruning of the intervals in which either no errorfree slots exist or an error-free slot exists in an earliest interval. In order to safely decide if an interval contains an error-free slot, we adapt the definition of maximal subtrees used for laminar instances as follows: given a set E of already queried errors, we say that a time interval In what follows, we consider the slots partitioned into groups: a slot t belongs to group G i , i ≥ 2, if the number of errors whose uncertainty area contain t is between 2 i-2 + 1 and 2 i-1 . For convenience, let G 0 and G 1 be the groups of slots that are contained to the uncertainty area of zero and one errors, respectively. The total number of groups is in O(log 2 k). Given two slots t, t with t ≤ t , let G i [t, t ] be the set of slots of group G i that appear in the interval (t -1, t ].

I = (t a , t b ] is maximal with respect to E if for each e ∈ E \ E either (s e , f e ] ⊆ (t a , t b ] or (s e , f e ] ∩ (t a , t b ] = ∅. Let E(I)
We define the middle slot of a set G i [t, t ] to be the slot in position |G i [t, t ]| /2 if we consider the slots in G i [t, t ] ordered from left to right with respect to the time-line.

In each iteration, the goal of our algorithm is to discover exactly one error-free slot: the earliest one which is not yet revealed. To do this, it performs a kind of binary search in the slots of the time horizon, starting from the slots of G 1 , then of G 2 , and so on. Specifically, the algorithm first considers the middle slot in G 1 and queries the error which contains it. Depending on the existence of at least one error-free slot on the left of the middle slot, we eliminate the interval on the right or on the left of this slot. The middle slot of the new interval that belongs to G 1 is sought, and we repeat the above procedure until the reduced interval does not contain any other slot of G 1 . Then, we continue the procedure by choosing the middle slot of the reduced interval that belongs to G 2 . If such a slot exists, we query all errors that contain it, and so on. Note that at the end of each step of the binary search, all errors containing the current middle slot are queried. However, we do not have to query again already queried errors. Algorithm 3 describes formally the above procedure.

Algorithm 3 Note that the intervals (lef t -1, right] in Lines 5 and 13 of Algorithm 3 are maximal with respect to the current set of errors E , and hence these two conditions can be justified as described in the beginning of the section. Theorem 6. Algorithm 3 is O(log 2 k)-competitive for the lexicographic error-query scheduling problem.

1: E ← ∅, SOL ← ∅ 2: for j ← 1 to n do 3: lef t ← 1, right ← last slot, f ound ← F alse, i ← 1 4: while f ound = F
Proof. By the definition of the problem, the algorithm and the adversary find exactly the same set of n error-free slots, let {t j1 , t j2 , . . . , t jn }. We consider these slots ordered with respect to the time-line. Note that the algorithm reveals them according to this order. Without loss of generality, we can assume that the adversary uses also the same order. Let E * , 1 ≤ ≤ n, be the set of errors queried by the adversary in order to reveal t j , without querying again the errors in E *

1 ∪ E * 2 ∪ . . . ∪ E * -1 . Then, the optimal solution queries n =1 |E * | errors. In a similar way, let E , 1 ≤ ≤ n, be the set of errors queried by the algorithm in iteration , i.e., the algorithm queries n =1 |E | errors. Since both the algorithm and the adversary reveal the slots in the same order and do not query again already queried errors, we can assume that after revealing the slot t j the instance is reduced by eliminating the queried errors (see Line 7 of the algorithm). Moreover, we consider that the groups G i are appropriately updated. Assume that the slot t j , 1 ≤ ≤ n, belongs to the group G i at the iteration during which it is revealed. If i = 0, then both algorithm and adversary does not query any additional error. If i ≥ 1, then the adversary queries at least 2 i -2 + 1 errors, while the algorithm at most i i=1 2 i-1 log 2 |G i | ≤ 2 i log 2 k additional errors. Therefore, the algorithm queries at most a factor of 4 log 2 k more errors than the adversary for revealing each error-free slot, and hence the theorem follows.

Conclusion

In this paper, we gave a polynomial-time algorithm for the off-line error-query scheduling problem. For the on-line version of the problem, we proved that the competitive ratio of any on-line algorithm is Ω( √ k) even if the instance is laminar, or agreeable and even if we search for only one free slot. Then, we proposed on O( √ k)-competitive algorithm for laminar instances. Finally, we studied the on-line lexicographic error-query scheduling problem and we proved that its competitive ratio is in Θ(log 2 n). A research question that remains open is the development of efficient on-line algorithms for general instances for the error-query scheduling problem. Going further, studying non-preemptive jobs of arbitrary processing times is an interesting direction.

Figure 1 :

 1 Figure 1: A laminar instance and its representation as a forest.

Figure 2 :

 2 Figure 2: An instance of the error-query scheduling problem for which the adversary queries only one error while it can oblige any on-line algorithm to query √ k errors.

Figure 3 :

 3 Figure 3: An agreeable instance of the lexicographic error-query scheduling problem for which the adversary queries at most two errors while it can oblige any on-line algorithm to query log 2 k errors.

  be the set of errors in E \ E that satisfy the first condition, i.e., e ∈ E(I) if (s e , f e ] ⊆ (t a , t b ]. Then, the number of error-free slots in I is equal to (t b -t a ) -|E(I)| -c, where c is the number of errors in E whose slot of appearance occurs in I.

Table 1 :

 1 Table 1 summarizes our results. Summary of results. We define the set I = {I 1 , I 2 , . . . , I |I| } of elementary intervals where |I|= |T | -1 and each I i , 1 ≤ i ≤ |I|, spans in [t i , t i+1 ].Note that the number of elementary intervals is at most twice the number of errors, i.e., |I| = O(k). Let E(I i ) be the set of errors whose span includes the elementary interval I i . Moreover, let F (E ) be the set of error-free slots that are revealed if we query the errors of the set E ⊆ E.

		Error-query			Lexicographic
		scheduling			error-query
						scheduling
		Lower	Upper	Lower	Upper
		Bound	Bound	Bound	Bound
	general agreeable laminar	Ω(	√ k)	--O( √	k)	Ω(log 2 k) O(log 2 k) optimal
	2 Preliminaries
	Let's consider the set T = {t 1 , t 2 , . . . , t |T | } of all s i 's and
	f i 's sorted in increasing order (we eliminate all duplicate val-
	ues).

  mid ← the middle slot of Gi[lef t, right] 12:Query all errors in E \ E that contain mid and add them to E 13:if there is an error-free slot t ∈ SOL with lef t ≤ t ≤

		then
	6:	SOL ← SOL ∪ {t}, f ound ← T rue
	7:	Update the groups Gi with respect to the new errors
		added in E during current iteration
	8:	else if |Gi[lef t, right]| ≤ 2 then
	9:	i ← i + 1
	10:	else
	11:
		right then
	14:	right ← mid
	15:	else
	16:	lef t ← mid

alse do 5:

if there is an error-free slot t ∈ SOL with lef t ≤ t ≤ right such that there is no error-free slot t ∈ SOL with lef t ≤ t ≤ t -1 and all errors containing t are in E

Acknowledgments

This work has been supported by the French ANR-14-CE24-0007-01 project "CoCoRICo-CoDeC" and by a LIP6 project.