domain: info math

text:
Pascale Bendotti
email: pascale.bendotti@edf.fr

Philippe Chrétienne
email: philippe.chretienne@lip6.fr

Pierre Fouilhoux
email: pierre.fouilhoux@lip6.fr

Adèle Pass-Lanneau
email: adele.pass-lanneau@edf.fr

Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem

Keywords: project scheduling, combinatorial optimization, mixed-integer programming, robust 2-stage optimization, polyhedral characterization

In project scheduling under processing times uncertainty, the Anchor-Robust Project Scheduling Problem is to find a baseline schedule of bounded makespan and a max-weight subset of jobs whose starting times are guaranteed. The problem was proven NP-hard even for budgeted uncertainty. In the present work we design mixed-integer programming (MIP) formulations that are valid for a variety of uncertainty sets encompassing budgeted uncertainty. A new dominance among solutions is proposed, resulting into an MIP formulation. We further study the combinatorial structure of the problem. Non-trivial polynomial cases under budgeted uncertainty are exhibited, where the dominance-based formulation yields a polyhedral characterization of integer solutions. In more general cases, the dominance-based formulation is shown to be tighter than all previously known formulations. In numerical experiments we investigate how the formulation performs on instances around the polynomial cases, for both budgeted uncertainty sets and more elaborate uncertainty sets involving several budgets.

Introduction

Consider a set of n jobs J to be scheduled under precedence constraints. The precedence graph is a directed acyclic graph G(p) = (J, A, p), where J = J ∪ {s, t} and s (resp. t) is a dummy job representing the beginning (resp. end) of the project. Processing times of jobs are p ∈ R J + and every arc (i, j) ∈ A has length p i , with p s = 0. A schedule of G(p) is a vector x ∈ R J + of starting times such that x s = 0 and x j -x i ≥ p i for every arc (i, j) of G(p). Finding a schedule with minimum makespan x t = min i∈J x i + p i is a classical polynomial-time solvable problem [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF].

In practice processing times may be uncertain parameters, which calls for robust approaches. We consider that jobs have nominal processing times p and the real processing times may be p + δ, where δ lies in an uncertainty set ∆ ⊂ R J + . For a given uncertainty set, different robust approaches can be considered. A first approach from the static-robust framework [START_REF] Soyster | Technical note -convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF] is to find a schedule x ∈ R J + such that x is a schedule of G(p+δ) for every δ ∈ ∆, and so that the makespan of x is minimized. The static-robust approach is known to be overly conservative, i.e., it produces a schedule with a very large makespan. An alternate approach from adjustablerobust optimization [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], is to find the minimum value B such that for every δ ∈ ∆ there exists a schedule x δ ∈ R J + of G(p + δ) such that x δ t ≤ B. The adjustable-robust approach is appealing since it often gives a worst-case makespan that is significantly lower than the static-robust makespan. It was studied in [START_REF] Minoux | Robust linear programming with right-hand-side uncertainty, duality and applications[END_REF] for project scheduling. A major drawback is that the schedule depends on the uncertainty realization. In other words, starting times cannot be decided before δ is known.

Project scheduling has a large variety of practical applications such as planning industrial activities. The durations of activities are often not known exactly or they can change over time: this calls for the study of project scheduling under processing times uncertainty. It is often necessary to compute a schedule in advance, called baseline schedule [START_REF] Herroelen | Project scheduling under uncertainty: Survey and research potentials[END_REF], while taking into account processing times uncertainty. The precomputation of a baseline schedule is common practice, especially when scheduling activities requires preparation and coordination with other entities to secure the availability of staff or specific equipment. The makespan of the baseline schedule is a major criterion; in some cases, the project must be scheduled so that it completes before a deadline. Moreover if processing times are disrupted and the schedule must be revised, it is important to stick to the baseline schedule [START_REF] Herroelen | The construction of stable project baseline schedules[END_REF]. As some activities may be difficult to reschedule, it is interesting to guarantee their starting times in the baseline schedule against uncertainty realizations.

The Anchor-Robust Project Scheduling Problem. A new robust problem was introduced in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF]. Before the real processing time of jobs is known, the problem is to decide which solution x of G(p) to choose as a baseline schedule with a bounded makespan. The key idea is to define an anchored set of jobs as a subset of jobs whose starting times could remain the same for any realization in the uncertainty set. Formally, given a schedule x of G(p) and uncertainty set ∆, a subset of jobs H ⊆ J is x-anchored if for every δ ∈ ∆ there exists x δ schedule of G(p+δ) such that x δ i = x i for every i ∈ H. Given a deadline for the project and an anchoring weight associated to each job, the Anchor-Robust Project Scheduling Problem (AnchRob) is then to find a baseline schedule x satisfying the deadline, and a subset of jobs H that is x-anchored, so as to maximize the total anchoring weight of H.

Connections with classical robust approaches are as follows. If there exists a solution (x, H) of (AnchRob) with H = J, i.e., a solution where all jobs are anchored, then x is a solution of the static-robust problem. If no such solution exists, it means that no static-robust solution respects deadline M . (AnchRob) is a so-called robust 2-stage optimization problem, where x and H are first-stage decisions and x δ are second-stage decisions. Schedule x is thus a baseline schedule which may be adjusted in second stage by revising starting times of non-anchored jobs only.

Let us present several uncertainty sets of interest for (AnchRob). This includes budgeted uncertainty sets [START_REF] Bertsimas | The price of robustness[END_REF] where at most Γ processing times deviate from the nominal values p. A special case is box uncertainty sets, in which every processing time deviates from its nominal value within an interval, corresponding to uncertainty budget Γ = n. Another special case, referred to as 1-disruption uncertainty sets, is also considered. It corresponds to the situation where one deviation of fixed length occurs to any job in the project (i.e., one job, whichever it could be). We also consider more elaborate uncertainty sets, corresponding to unions or intersections of budgeted uncertainty sets. Such uncertainty sets account, e.g., for the case of several uncertainty budgets on subsets of jobs.

Robust 2-stage problems are often considered challenging and computationally intensive [START_REF] Buchheim | Robust combinatorial optimization under convex and discrete cost uncertainty[END_REF]Kurtz, 2018, Gabrel et al., 2014]. A compact MIP formulation for robust 2-stage problems is often not known, and proposed exact approaches rely on decomposition methods, see, e.g., [START_REF] Billionnet | 2-stage robust MILP with continuous recourse variables[END_REF][START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF][START_REF] Zeng | Solving two-stage robust optimization problems using a column-andconstraint generation method[END_REF]. Another trend is to consider approximations. With decision rules introduced in Ben-Tal et al. [2004] it is assumed that second-stage variables have a fixed dependency (e.g., affine) on the uncertainty realization. It yields tractable approximations of the original robust 2-stage problem. With kadaptability introduced by [START_REF] Bertsimas | Finite adaptability in multistage linear optimization[END_REF] a fixed number of recourse solutions is determined in first stage and the recourse problem is to choose the best among them. The focus of the present work is to investigate exact approaches for the (AnchRob) problem, and especially compact formulations, which -to the best of our knowledge -have been scarcely studied for robust 2-stage problems.

Robust 2-stage problems including a baseline solution in first stage and a feature to keep decisions unchanged were considered under the name of recoverable robustness [START_REF] Liebchen | The concept of recoverable robustness, linear programming recovery, and railway applications[END_REF][START_REF] Gianlorenzo | Recoverable robust timetables: An algorithmic approach on trees[END_REF] or robust optimization with incremental recourse [S ¸eref et al., 2009]. When decisions are represented by continuous variables, different measures can be used to account for the stability of decisions. For project scheduling, the expected absolute gap between starting times was used as stability measure in [START_REF] Herroelen | The construction of stable project baseline schedules[END_REF]. The anchoring criterion was defined as the number of identical starting times in [START_REF] Bendotti | Anchored reactive and proactive solutions to the CPM-scheduling problem[END_REF]. This criterion was studied for rescheduling problems in [START_REF] Bendotti | Anchored rescheduling problems under generalized precedence constraints[END_REF]. The (AnchRob) problem was introduced in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF], and it was proven NP-hard even for budgeted uncertainty. For budgeted uncertainty, a compact MIP reformulation was obtained, denoted by (Lay). It is based on a so-called layered graph and a dedicated analysis of the problem in this special case. This MIP formulation is inherent to budgeted uncertainty, and thus not applicable to other uncertainty sets.

In this work, we investigate linear formulations for (AnchRob) that are valid for a variety of uncertainty sets encompassing budgeted uncertainty. The starting point is to precompute the worst-case value over ∆ of the longest i-j path for every pair of jobs i, j, and to use these values in a linear formulation. We exhibit a dominance property among schedules and derive a linear formulation from it. This dominance-based linear formulation, called (Dom), improves over a naive linear formulation. In the case of budgeted uncertainty, (Dom) is compared with known formulation (Lay). A polyhedral study is carried out to highlight how formulation (Dom) captures the combinatorial structure of the problem. We prove that (Dom) yields a complete polyhedral characterization in two special cases: box uncertainty, and 1-disruption uncertainty for precedence graphs where all s-t paths are longest s-t paths. We thus obtain that the latter is a polynomial case, while (AnchRob) under budgeted uncertainty is NP-hard in general. Finally numerical experiments give evidence that (Dom) performs well for budgeted uncertainty, even for instances that do not match the polyhedral characterization cases. (Dom) is also capable of solving the problem for uncertainty sets where no MIP formulation was previously investigated, e.g., in the case of several budgets.

In Section 2 notation and preliminaries on problem (AnchRob) are given. In Section 3 the dominance-based linear formulation is presented, and compared with other known formulations. In Section 4 polyhedral characterizations are proven for box uncertainty, and 1-disruption uncertainty. In Section 5 numerical results are presented.

Preliminaries

General notation

Let G(p) = (J, A, p) be the precedence graph. It is assumed that there is an arc (s, i) (resp. an arc (i, t)) for every job i ∈ J without predecessor (resp. without successor) in J. Let ≺ denote the partial order on J defined by i ≺ j if there exists an i-j path in G. Given i, j ∈ J, i ≺ j, let L G(p) (i, j) be the length of the longest i-j path in G(p). In the sequel we will use the shorthand notation L 0 ij = L G(p) (i, j). The minimum makespan of a schedule of G(p) is then L 0 st . The earliest schedule defined by

x i = L 0 si for every i ∈ J is a schedule with minimum makespan. Let X ≤M ⊆ R J + denote the set of schedules of G(p) with makespan at most M . A longest s-t path is a critical path. The precedence graph G(p) is quasi-critical if every job i ∈ J belongs to a critical path, i.e., L 0 si + L 0 it = L 0 st . The precedence graph G(p) is critical if all s-t paths in G(p) are critical, i.e., they have length L 0 st . Note that if G(p) is critical then it is quasi-critical.
The uncertainty set ∆ is assumed to be a subset of R J + . For uncertainty set ∆, let us define the value

L ∆ ij = max δ∈∆ L G(p+δ) (i, j)
for every i, j ∈ J, i ≺ j. Then L ∆ ij is the worst-case longest path value between job i and job j.

The Anchor-Robust Project Scheduling Problem

Let us now give a formal definition of the Anchor-Robust Project Scheduling Problem (An-chRob). An instance of the problem is described by the parameters (G(p), M, ∆, w) where: G(p) = (J, A, p) is the precedence graph, M ≥ 0 is a deadline on the project, ∆ ⊂ R J + is the uncertainty set, and w ∈ R J + is a vector of non-negative anchoring weights associated with jobs. A solution of the problem is a pair (x, H) where x is a schedule of G(p) with makespan x t at most M , and H is a subset of J that is x-anchored, that is: for every realization δ in ∆, there exists a schedule x δ of G(p + δ) satisfying x δ i = x i for i ∈ H. The objective is to find a solution (x, H) with maximum total anchoring weight i∈H w i .

The Anchor-Robust Project Scheduling Problem is related to robust 2-stage optimization. First-stage decisions are the baseline schedule x, and the anchored set H. Second-stage decisions, i.e., decisions that depend on the uncertainty realization, are the schedule x δ involved in the definition of an anchored set. The problem can be rewritten under the following form:

(AnchRob): max i∈H w i s.t. x schedule of G(p) x t ≤ M H ⊆ J: ∀δ ∈ ∆, ∃ x δ schedule of G(p+δ) s.t. x i = x δ i ∀i ∈ H
Note that the proposed form is related to max/min/max problems arising usually in robust 2stage optimization. Given a schedule x of G(p), a subset H ⊆ J, and an uncertainty realization δ ∈ ∆, the second-stage or recourse problem of (AnchRob) is to decide the existence of a schedule x δ of G(p + δ) with x i = x δ i for every i ∈ H. Let us finally illustrate (AnchRob) on a simple example. Consider a project scheduling instance with 5 jobs. The precedence graph is represented in Figure 1. Nominal processing times are p = (1, 1, 1, 1, 2). Each job is also associated with a worst-case deviation δ = (0.5, 1, 0.5, 0.5, 0.5). In Figure 1, each arc (i, j) is weighted with value p i + δ i . Let the deadline be M = 4.5. Two different uncertainty sets will be considered, to give a flavor of their respective impact on solutions of (AnchRob).

A first uncertainty set is the box ∆ = Π i∈J [0, δ i ]. Then every job i may have any duration in range [p i , p i + δ i ]. Consider a schedule for processing times p+ δ. If it has a makespan larger than M , such a schedule is infeasible for (AnchRob). Hence (AnchRob) is different from the staticrobust case. Consider the schedule x = (0, 1, 1, 3, 2.5) and set H = {1, 2, 4}. Figure 2 shows schedule x. Each job is represented by a rectangle of length p i , and deviation δ i is represented with dotted rectangle. Jobs from H are represented in dark gray. Then (x, H) is a solution of (AnchRob) for box ∆. First x has makespan M = 4.5. Also the set H is x-anchored, since for any value of jobs durations, it is possible to repair the schedule by moving jobs 3 and 5 only (in this case, just by right-shifting). A second uncertainty set is ∆ = {( δ i u i ) i∈J : u ∈ {0, 1} J , i∈J u i ≤ 1}. It corresponds to an uncertainty budget Γ = 1, i.e., at most one processing time deviates. Consider the same schedule x, and the set H = {1, 2, 4, 5}, represented in Figure 3. Set H is x-anchored for budgeted uncertainty set ∆: indeed for any value of δ ∈ ∆, the schedule can be repaired by moving only job 3.

= {( δ i u i ) i∈J : u ∈ {0, 1} J , i∈J u i ≤ 1}.

Uncertainty sets

Note first that some assumptions on ∆ can be made without loss of generality. The uncertainty set can be assumed to be convex [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. The uncertainty set can also be assumed to be down-monotone, i.e., if δ ∈ ∆ and δ ≤ δ then δ ∈ ∆. Indeed it directly follows from the fact that if x δ is a schedule of G(p + δ), then it is a schedule of G(p + δ ) for every δ ≤ δ. In the present work, considered uncertainty sets will be polyhedra, and w.l.o.g. down-monotone.

Let us now present some uncertainty sets of interest.

Set ∆ is a box uncertainty set if ∆ = {(δ i ) i∈J : 0 ≤ δ i ≤ δ i ∀i ∈ J} with δ ∈ R J + , i.e.
, it is a cartesian product of intervals. Then δ is a greatest element of ∆ in the sense that δ ≤ δ for every δ ∈ ∆. Note that if ∆ is any set with greatest element δ, then w.l.o.g. it can be assumed to be down-monotone, and thus equal to the box with greatest element δ.

Set ∆ is a budgeted uncertainty set if ∆ = {( δ i u i ) i∈J : u ∈ [0, 1] J , i∈J u i ≤ Γ}, with deviation δ ∈ R J + and uncertainty budget Γ ∈ {1, . . . , |J|}. The extreme points of such ∆ correspond to budgeted uncertainty as defined in the seminal work of [START_REF] Bertsimas | The price of robustness[END_REF], where Γ is the number of processing times that may deviate from their nominal value. Box uncertainty is the special case of budgeted uncertainty where Γ = |J|.

Set ∆ is a 1-disruption uncertainty set if it is a budgeted uncertainty set with unit budget Γ = 1 and uniform deviation, i.e., δ i = δ 0 for every i ∈ J. Extreme points of a 1-disruption uncertainty set represent the situation where one event of fixed -possibly large -deviation δ 0 may happen anywhere in the project. Then the processing time of one job is increased by fixed amount δ 0 .

Let us now present more elaborate uncertainty sets, built as unions or intersections of budgeted uncertainty sets.

Set ∆ is a partition-budgeted uncertainty

set if ∆ = {( δ i u i ) i∈J : u ∈ [0, 1] J , i∈J k u i ≤ Γ k ∀k ∈ {1, . . . , m}} where (J 1 , ..., J m ) is a partition of J and Γ k ∈ {1, . . . , |J k |} for every k ∈ {1, . . . , m}. Each group J k is associated with its own uncertainty budget Γ k . It holds that ∆ = 1≤k≤m ∆ k where ∆ k = {( δ i u i ) i∈J : u ∈ [0, 1] J , i∈J k u i ≤ Γ k } for every k ∈ {1, .
. . , m}. Distinct uncertainty budgets on disjoint subsets of the partition are relevant when deviations of jobs from different subsets are uncorrelated. A special case of interest is to consider a partition (J 1 , J 2 ) where jobs of the first subset J 1 are associated with small deviations but large uncertainty budget Γ 1 ; jobs of the second subset J 2 are associated with large deviations but small uncertainty budget Γ 2 .

Set ∆ is a mixed-budgeted uncertainty set if ∆ = 1≤k≤m ∆ k where ∆ k are budgeted uncertainty sets. Consider the following special case, where ∆ 1 is defined by deviation δ and budget Γ 1 , and ∆ 2 is defined by deviation τ δ for a given τ ∈ [0, 1], and budget Γ 2 > Γ 1 . Then ∆ = ∆ 1 ∪ ∆ 2 supports two kinds of uncertainty realizations corresponding either to a large number of small deviations (i.e., δ ∈ ∆ 2 ) or a small number of large deviations (i.e., δ ∈ ∆ 1 ).

For uniform deviation, it holds that ∆ 1 ∆ whenever τ Γ 2 > Γ 1 .

All these uncertainty sets are defined implicitly through inequalities or set operations. Note that the uncertainty set may also be given explicitly as the convex hull of a discrete set of points. Given a set S of scenarii, for every s ∈ S the uncertainty realization is some δ s ∈ R J + , and ∆ = conv{δ s , s ∈ S}. Any implicitly-defined set ∆ can be written under that form by enumerating its extreme points, but then the input size is exponentially increased.

Assumption on longest paths computation

Computing worst-case longest path values L ∆ ij can be an NP-hard problem for polyhedral set ∆ defined by inequalities [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF].

However, efficient algorithms can be designed for some uncertainty sets. For box uncertainty, the computation is straightforward since

L ∆ ij = L G(p+ δ) (i, j).
For budgeted uncertainty sets, and thus 1-disruption uncertainty sets, the worst-case longest path values L ∆ ij can be computed in polynomial time by dynamic programming [START_REF] Minoux | Robust linear programming with right-hand-side uncertainty, duality and applications[END_REF]. The algorithm is linear in Γ|A|. For partition-budgeted uncertainty sets, the L ∆ ij values can be computed using a straightforward generalization of the dynamic programming of [START_REF] Minoux | Robust linear programming with right-hand-side uncertainty, duality and applications[END_REF] which is linear in (Π 1≤k≤m Γ k )|A|. For mixed-budgeted uncertainty sets, the L ∆ ij values can be easily obtained since

L ∆ ij = max 1≤k≤m L ∆ k ij for every i, j ∈ J. For explicitly-defined uncertainty sets, values L ∆ ij can be computed in polynomial time in the number of scenarii |S|, since L ∆ ij = max s∈S L G(p+δ s ) (i, j). This relies on the property that L ∆ ij = L conv(∆) ij
for any ∆, as proven in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF].

In the sequel, the main assumption is that the L ∆ ij values have been precomputed. Thus they will appear as coefficients of constraints in the proposed mixed-integer programming formulations.

Anchored sets

Let us finally give some preliminaries related to linear formulations for (AnchRob). Recall that a solution of (AnchRob) is a pair (x, H) with a schedule x and a subset H of jobs that is xanchored. Fix x a schedule of G(p). It was shown in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF] that a set H is x-anchored if and only if

x j -x i ≥ L ∆ ij for every i ∈ H ∪ {s}, j ∈ H, i ≺ j. Let G H denote the precedence graph obtained from G(p) by introducing additional arcs (i, j), i ∈ H ∪ {s}, j ∈ H, i ≺ j with arc-lengths L ∆ ij . Then Proposition 1 (Bendotti et al. [2019]). Let H ⊆ J. Vector x is a schedule of G(p) such that H is x-anchored if and only if x is a schedule of G H .
Let us now define anchored sets, independently from a given baseline schedule. A subset H ⊆ J is anchored if there exists a schedule x of G(p) with makespan at most M such that H is xanchored. An issue is then to retrieve a baseline schedule x for which H is x-anchored. Consider z the earliest schedule of G H : then by Proposition 1, if H is an anchored set then H is z-anchored. Given H ⊆ J, let χ H denote the incidence vector of H. Let H = {χ H : H anchored set}, and Q = conv(H). Note that (AnchRob) reduces to finding a max-weight anchored set, i.e., maximizing i∈J w i h i for h ∈ H, or equivalently, for h ∈ Q.

Let us give some definitions related to mixed-integer programming formulations for (An-chRob). Considered formulations for (AnchRob) involve binary anchoring variables h ∈ {0, 1} J to indicate if jobs are in the anchored set, and continuous variables, say x ∈ R q . A formulation for (AnchRob) is defined by a polyhedron P ⊆ R q × [0, 1] J and integrality constraints h ∈ {0, 1} J , so that the feasible set of the formulation is P ∩ (R q ×{0, 1} J ). Given F ⊆ R q × R J , let Proj h (F) = {h ∈ R J : ∃(x, h) ∈ F} denote its projection on h variables. A formulation is valid for (AnchRob) if Proj h (P) ∩ {0, 1} J = H. Given two polyhedra P 1 and P 2 , formulation associated with P 1 is stronger than formulation associated with P 2 if Proj h (P 1 ) ⊆ Proj h (P 2 ). A formulation yields a polyhedral characterization for (AnchRob) if Proj h (P) = Q. Importantly, if the formulation associated with polyhedron P yields a polyhedral characterization for a special case of (AnchRob), and P is described by a polynomial number of inequalities, then the special case of (AnchRob) is polynomial. Indeed (AnchRob) can be solved by the linear program max i∈J w i h i for (x, h) ∈ P.

3 Linear formulations for (AnchRob)

In this section, we establish linear formulations for (AnchRob) using L ∆ ij values as coefficients. In Section 3.1 a naive formulation is given as a benchmark. In Section 3.2 the main dominance property is proven. In Section 3.3 a formulation is derived from the dominance property. In Section 3.4 it is compared with other known formulations.

A naive formulation

Consider schedule continuous variables x j , j ∈ J, and anchoring binary variables h j ∈ {0, 1}, j ∈ J. Vector h is the incidence vector of the anchored set H. A formulation for (AnchRob) requires constraints to enforce that H is an x-anchored set. The characterization of Proposition 1 suggests a quadratic constraint

x j -x i ≥ L ∆ ij h i h j ∀i, j ∈ J, i ≺ j (1)
to represent precedence constraints of the graph G H . Note that for dummy jobs s and t there is no h j decision variable but we set h s = 1 and h t = 0 for the ease of notation. For validity, it is sufficient to check that for each i ≺ j, if h i = 0 or h j = 0 then inequality (1) is valid. Indeed it reduces to x j -x i ≥ 0 which holds for every i ≺ j for every schedule x of G(p).

Applying a standard linearization technique, a linear formulation (Std) can be obtained by replacing constraint (1) by the following linear inequality (2)

(Std): max i∈J w i h i s.t. x j -x i ≥ p i ∀(i, j) ∈ A x t ≤ M x j -x i ≥ L ∆ ij (h i + h j -1) ∀i, j ∈ J, i ≺ j (2) x j ≥ 0 ∀j ∈ J h j ∈ {0, 1} ∀j ∈ J
It is easy to check that when h i = 0 or h j = 0, (2) induces a valid constraint.

A dominance property

Let H ⊆ J be a subset of jobs. Let us define the set of all baseline schedules x such that (x, H) is feasible for (AnchRob) as

X ≤M (H) = {x ∈ X ≤M : H x-anchored}. Note that (AnchRob)
problem is to maximize the weight of a set H such that X ≤M (H) = ∅. By Proposition 1,

X ≤M (H) = {x ∈ X ≤M : x j -x i ≥ L ∆ ij ∀i ∈ H ∪ {s}, j ∈ H, i ≺ j}.
Let us now define a set of baseline schedules where the same inequality is imposed, but on pairs i, j with i ∈ J ∪ {s}:

Z ≤M (H) = {z ∈ X ≤M : z j -z i ≥ L ∆ ij ∀i ∈ J ∪ {s}, j ∈ H, i ≺ j}. Theorem 1. Set Z ≤M (H) is dominant, in the sense that Z ≤M (H) ⊆ X ≤M (H), and X ≤M (H) = ∅ implies Z ≤M (H) = ∅.
Proof. Since H ⊆ J, the definition of set Z ≤M (H) contains more constraints than that of set

X ≤M (H). Hence Z ≤M (H) ⊆ X ≤M (H). Let us prove X ≤M (H) = ∅ =⇒ Z ≤M (H) = ∅. Note that X ≤M (H)
i = L G (s, i) = L G (s, k) + L G (k, i) = z k + L G (k, i). The subpath of P * si from k to i is a longest k-i path in G H . Since it has no vertex in H ∪ {s} except k, it uses no additional arc and its length is L G (k, i) = L 0 ki . It comes z k -z i = -L 0 ki . Since z ∈ X ≤M (H), z j -z k ≥ L ∆ kj . Then z j -z i = (z j -z k )+(z k -z i ) ≥ L ∆ kj -L 0 ki . Also, for k ≺ i ≺ j, it holds that L ∆ kj ≥ L 0 ki +L ∆ ij : indeed L ∆ ij is attained for some δ * ∈ ∆ ⊆ R J + , hence L ∆ kj ≥ L G(p+δ * ) (k, i) + L G(p+δ * ) (i, j) ≥ L 0 ki + L ∆ ij . Finally z j -z i ≥ L ∆ ij , hence z ∈ Z ≤M (H).

Dominance-based linear formulation (Dom)

(AnchRob) problem is to maximize the weight of a set H such that X ≤M (H) = ∅, or equivalently with Theorem 1, such that Z ≤M (H) = ∅. We now introduce a new formulation derived from Theorem 1, where continuous variables z correspond to a schedule z ∈ Z ≤M (H).

(Dom): max

i∈J w i h i s.t. z j -z i ≥ p i ∀(i, j) ∈ A z t ≤ M z j -z i ≥ L 0 ij + (L ∆ ij -L 0 ij )h j ∀i, j ∈ J, i ≺ j (3) z j ≥ 0 ∀j ∈ J h j ∈ {0, 1} ∀j ∈ J Proposition 2. Formulation (Dom) is valid for (AnchRob).
Proof. Let (z, h) be feasible for (Dom), and

H := {i ∈ J : h i = 1}. Note first that inequality (3) implies z ∈ X ≤M (H).
Hence z is a schedule with makespan at most M and H is z-anchored.

Hence h ∈ H. Conversely, let h ∈ H be the incidence vector of an anchored set H. From Prop. 1 and Theorem 1, there exists z ∈ Z ≤M (H). Such a schedule z satisfies z j -

z i ≥ L ∆ ij for every i ∈ J ∪ {s} and j ∈ H. Then z satisfies (3): indeed if h j = 1 inequality (3) corresponds to inequality z j -z i ≥ L ∆ ij ; if h j = 0 then (3) amounts to z j -z i ≥ L 0 ij , which holds since z is a schedule of G(p).
Note that precedence constraint z j -z i ≥ p i associated with arc (i, j) ∈ A is implied by (3) since i ≺ j and L 0 ij ≥ p i .

We now introduce a family of valid inequalities. Let j ∈ J. By inequality (3

) with i = s, it comes that z j ≥ L 0 sj + (L ∆ sj -L 0 sj )h j . Since z ∈ X ≤M it satisfies z j + L 0 jt ≤ M , thus leading to M ≥ L 0 sj + (L ∆ sj -L 0 sj )h j + L 0 jt .
Hence the following valid inequality

h j ≤ M -(L 0 sj + L 0 jt ) L ∆ sj -L 0 sj . (4)
In Section 4 they will be discussed with respect to the polyhedral characterization under box uncertainty.

Comparison with known formulations

In this section formulation (Dom) is compared with (Std) and with (Lay), the previously known formulation from [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF] dedicated to budgeted uncertainty.

Consider first the continuous relaxations of (Dom), (Std) and the variant of (Std) with quadratic constraint [START_REF] Minoux | Robust linear programming with right-hand-side uncertainty, duality and applications[END_REF]. It turns out that they can easily be compared. Indeed for every h i , h j ∈ [0, 1], it holds that h j ≥ h i h j . Hence the right-hand side of inequality (3) is tighter than the right-hand side of inequality [START_REF] Minoux | Robust linear programming with right-hand-side uncertainty, duality and applications[END_REF]. Also for every h i , h j ∈ [0, 1], it holds that (1-h i )(1-h j ) ≥ 0 or equivalently h i h j ≥ h i + h j -1. Hence the right-hand side of inequality ( 1) is tighter than the right-hand side of inequality (2).

Let us now investigate the special case of budgeted uncertainty, and compare (Dom) with formulation (Lay) from [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF], that we now recall. Formulation (Lay) involves anchoring variables h j ∈ {0, 1} for every j ∈ J, and continuous variables x γ j for every γ ∈ {0, . . . , Γ}, j ∈ J. Formulation (Lay) is based on a so-called layered graph G lay (h) associated with h ∈ [0, 1] J and built as follows. The layered graph G lay (h) is formed with Γ + 1 copies of the precedence graph called layers indexed from 0 to Γ. Let i γ denote the copy of job i in layer γ. The layered graph features three types of arcs. Horizontal arcs are copies of arcs of G(p), i.e., arcs (i γ , j γ ) for (i, j) ∈ A, with length p i . Transversal arcs are (i γ+1 , j γ ) for (i, j) ∈ A, with length p i + δ i . Vertical arcs are (i γ , i Γ ) for i ∈ J, γ < Γ, with length -D j (1 -h j ), where D j = L G(p+ δ) (s, j) -L G(p) (s, j) for every j ∈ J. It was shown that h ∈ {0, 1} J is the incidence vector of an anchored set if and only if there exists x a schedule of G lay (h) such that x Γ t ≤ M . This leads to the formulation (Lay): max

i∈J w i h i s.t. x γ j -x γ i ≥ p i ∀(i, j) ∈ A, ∀γ ∈ {0, . . . , Γ} x γ j -x γ+1 i ≥ p i + δ i ∀(i, j) ∈ A, ∀γ ∈ {0, . . . , Γ -1} x Γ j -x γ j ≥ -D j (1 -h j ) ∀j ∈ J, ∀γ ∈ {0, . . . , Γ -1} x Γ t ≤ M x γ j ≥ 0 ∀j ∈ J, ∀γ ∈ {0, . . . , Γ} h j ∈ {0, 1} ∀j ∈ J
Variables x Γ j , j ∈ J from layer Γ can be thought of as a baseline schedule such that H = {i ∈ J : h i = 1} is x Γ -anchored. Other continuous variables x γ j , j ∈ J, γ < Γ can be regarded as additional variables.

In order to compare linear relaxations of (Lay) and (Dom), we show how to project explicitly those two formulations on the space of h variables. Let C be the set of s-t paths in the transitive closure of G. Note that there is one-to-one correspondence with chains of the poset (J, ≺). Let P Lay (resp. P Dom ) denote the polytope of solutions ((x γ ) γ∈{0,...,Γ} , h) (resp. (z, h)) that are feasible for the continuous relaxation of formulation (Lay) (resp. (Dom)).

Proposition 3.

Proj h (P Dom ) =        h ∈ [0, 1] J : (i,j)∈C j =t L 0 ij + (L ∆ ij -L 0 ij )h j + L 0 j C t ≤ M ∀C ∈ C        Proj h (P Lay ) =        h ∈ [0, 1] J : (i,j)∈C j =t L ∆ ij -D j (1 -h j ) + L 0 j C t ≤ M ∀C ∈ C       
where j C denotes the last vertex of path C before sink t.

Proof. Let h ∈ [0, 1] J . Let G(h) denote the transitive closure of G, where arc (i, j) is given the weight L 0 ij + (L ∆ ij -L 0 ij )h j
, with h t = 0 for the ease of notation. Then (z, h) ∈ P Dom if and only if z is a schedule of G(h) with makespan z t ≤ M , by definition of formulation (Dom). The existence of such z is equivalent to L G(h) (s, t) ≤ M ; or equivalently, every s-t path in G(h) has length at most M . The length of path C ∈ C in G(h) is exactly the left-hand side of the proposed inequality, hence the result.

A similar proof holds for formulation (Lay). Let h ∈ [0, 1] J . Let G lay (h) (R) denote the length of a path R in the layered graph G lay (h). It holds that h ∈ Proj h (P Lay ) if and only if there exists x a schedule of G lay (h) such that x Γ t ≤ M . The existence of x is equivalent to the longest path condition:

L G lay (h) (s Γ , t Γ ) ≤ M ; or equivalently, G lay (h) (R) ≤ M for every path R from s Γ to t Γ in the layered graph G lay (h). Let us now show that it is equivalent to (i,j)∈C, j =t L ∆ ij -D j (1 -h j ) + L 0 j C t ≤ M for every C ∈ C. Assume first G lay (h) (R) ≤ M for every path R from s Γ to t Γ in G lay (h).
Let C ∈ C be an s-t path in the transitive closure of G. Consider an associated s Γ -t Γ path R * in the layered graph built as follows: for every arc (i, j) ∈ C, j = t, path R * contains the subpath of length L ∆ ij going from i Γ to a copy j γ of j, and the vertical arc (j γ , j Γ ); path R * also contains the subpath of length L 0 j C t going from j C Γ to t Γ . Then R * is an s Γ -t Γ path in G lay (h), by assumption it has length at most M , hence (i,j)∈C,

j =t L ∆ ij -D j (1 -h j ) + L 0 j C t ≤ M . Conversely assume (i,j)∈C, j =t L ∆ ij -D j (1 -h j ) + L 0 j C t ≤ M for every C ∈ C.
Let R be an s Γ -t Γ path in G lay (h). Let C * be the path defined the successive jobs j such that R contains a vertical arc (j γ , j Γ ); then C * ∈ C. For every (i, j) ∈ C * , let R (i,j) denote the subpath of R from i Γ to a copy j γ of job j. Since R (i,j) uses at most Γ transversal arcs, it comes

G lay (h) (R (i,j) ) ≤ L ∆ ij . Similarly, let R (j C * ,t) denote the subpath of R between j C * Γ and t Γ , then G lay (h) (R (j C * ,t) ) ≤ L 0 j C * t . The total length of R is G lay (h) (R) = (i,j)∈C * ,j =t ( G lay (h) (R (i,j) ) - D j (1 -h j )) + G lay (h) (R (j C * ,t) ), thus upper-bounded by (i,j)∈C * ,j =t (L ∆ ij -D j (1 -h j )) + L 0 j C * t . By assumption this at most M since C * ∈ C, hence G lay (h) (R) ≤ M . This proves the claimed result. Proposition 4. If the instance satisfies L G(p+ δ) (s, j) -L 0 sj ≥ L ∆ ij -L 0 ij
for every i ≺ j, then formulation (Dom) is stronger than formulation (Lay), in the sense that Proj h (P Dom ) ⊆ Proj h (P Lay ).

Proof. For every

i ≺ j, it holds that L ∆ ij -D j (1-h j ) ≤ L 0 ij +(L ∆ ij -L 0 ij )h j . Indeed it is equivalent to (D j -L ∆ ij + L 0 ij )h j ≤ D j -L ∆ ij + L 0 ij
. This latter inequality is satisfied for every h j ∈ [0, 1], since D j -L ∆ ij + L 0 ij ≥ 0 by the assumption. Using the explicit definition of projections in Prop. 3, it comes that the inequalities defining the projection of (Dom) are tighter than the inequalities defining the projection of (Lay).

Importantly, the assumption of Proposition 4 is satisfied if the precedence graph is critical. Indeed, assume G(p) is critical and let i ≺ j. The D j value satisfies

D j ≥ L ∆ sj -L 0 sj ≥ L 0 si + L ∆ ij -L 0 sj . Since G(p) is critical, it holds that L 0 si + L 0 ij = L 0 sj , hence D j ≥ L ∆ ij -L 0 ij
. We now give an example satisfying the assumption of Proposition 4, and where Proj h (P Dom ) is strictly included in Proj h (P Lay ). Let J = {1, 2, 3} be a set of three jobs, let G be the path (s, 1, 2, 3, t), and let p i = 1 and δ i = 1 for every i ∈ J. Let also Γ = 1, and M = 3. Consider h * = (1, 0, 12 ). To see that h ∈ Proj h (P Lay ), consider the layered graph G lay (h * ), represented in Figure 4. The vector x defined by x 1 = (0, 0, 1, 2, 3) in layer 1, x 0 = (0, 0, 2, 3, 4) in layer 0 is also represented into brackets on the vertices in Figure 4.

s 0 1 0 2 0 3 0 t 0 s 1 1 1 2 1 3 1 t 1 0 1 1 1 0 1 1 1 1 + 1 1 + 1 1 + 1 0 -1 -2(1-1 2 ) [0] [0] [1] [2] [3] [0] [0] [2] [3] [4]
Figure 4: Layered graph G lay (h * ) for h * = (1, 0, 1 2 ).

It can be checked that vector x is a schedule of G lay (h * ), hence (x, h * ) ∈ P Lay . By contrast, vector h * violates inequality defining Proj h (P Dom ) associated with path P = (s, 3, t). Indeed L 0 s3 = 2, L ∆ s3 = 3, L 0 3t = 1 and the inequality is 2 + h 3 + 1 ≤ 3. Thus h * / ∈ Proj h (P Dom ), and Proj h (P Dom ) Proj h (P Lay ). More precisely, it is a case where (Dom) yields a polyhedral characterization of (AnchRob), as shown next in Section 4.2.1.

The question whether (Dom) is stronger than (Lay) for any instance, is left open. However in numerical experiments presented in Section 5, the linear bound of (Dom) was always better than the linear bound of (Lay).

Polyhedral characterization for special cases

In this section, we provide polyhedral characterizations of (AnchRob) for two special cases: box uncertainty and 1-disruption uncertainty for critical precedence graph.

Box uncertainty

This section is devoted to box uncertainty, which is the special case of budgeted uncertainty where Γ = |J|, and thus δ ∈ ∆. Note first that if x the earliest schedule of G(p + δ) satisfies the deadline constraint x t ≤ M , then all jobs can be anchored and (x, J) is an optimal solution of (AnchRob). However in general the schedule x may have a makespan larger than M , hence not all jobs can be anchored (see, e.g., the example in Figure 2 in Section 2).

In [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF] a polynomial algorithm for (AnchRob) under box uncertainty was provided. This algorithm is as follows: compute x the earliest schedule of G(p + δ) and x the latest schedule of G(p) such that x t = M ; let H * = {i ∈ J | x i ≤ x i } and x i = min{x i , x i } for every i ∈ J; return (x, H * ).

The main result is that in this case the polytope Q of anchored sets is characterized by inequalities (4).

Theorem 2. For box uncertainty,

Q = {h ∈ [0, 1] J : h satisfies (4)}.
Proof. Consider schedules x and x, defined by x j = L G(p+ δ) (s, j) and x j = M -L 0 jt for every j ∈ J. Note first that for box uncertainty, L ∆ sj = L G(p+ δ) (s, j) = x j . Inequality (4) writes in this case:

h j ≤ M -(L 0 sj +L 0 jt ) L ∆ sj -L 0 sj = xj -L 0 sj x j -L 0 sj . Equivalently, it implies h j ≤ 1 if j ∈ H * , and h j ≤ 0 if j / ∈ H * . Hence {h ∈ [0, 1] J : h satisfies (4)} = [0, 1] H * × {0} J\H * .
Every extreme point of [0, 1] H * × {0} J\H * is the incidence vector of a set H ⊆ H * . Since any subset of an anchored set is anchored, and

H * is anchored, then [0, 1] H * × {0} J\H * ⊆ Q.
Conversely, if H is an anchored set, its incidence vector χ H satisfies valid inequalities (4): thus

H ⊆ H * . Hence Q ⊆ [0, 1] H * × {0} J\H * .
Note that Theorem 2 also holds for any ∆ that has a greatest element δ. This case is more general than ∆ being a box, as mentioned in Section 2.3.

1-disruption uncertainty

In this section, set ∆ is a 1-disruption uncertainty set, i.e., a budgeted uncertainty set with Γ = 1 and δ i = δ 0 for every i ∈ J. In Section 4.2.1 the polyhedral characterization is shown for the special case with zero processing times. In Section 4.2.2 it is extended to any critical precedence graph with non-zero processing times.

The Unitary (AnchRob)

Assume first p i = 0 for every i ∈ J. W.l.o.g. δ 0 = 1. Finally assume deadline M integer. If M is not integer, it can be replaced with M w.l.o.g.: indeed, since p and δ are integer, for any H the earliest schedule of G H is integer-valued with integer makespan.

In this special case, an instance is the precedence graph G = (J, A), p = 0, δ 0 = 1, integer deadline M , and anchoring weights. This special case is referred to as the Unitary Anchor-Robust (U-AnchRob) problem. For unit anchoring weights, it has been identified as a polynomial case in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF] by an equivalence with a problem on posets for which a min/max theorem is known [START_REF] Schrijver | Combinatorial Optimization -Polyhedra and Efficiency[END_REF].

For (U-AnchRob) our main result is a characterization of the polytope through formulation (Dom). It relies on the polyhedral result of Theorem 3. Let (J, ≺) be a poset with s (resp. t) a least (resp. greatest) element. Consider the inequalities

z i -z s ≥ 0 ∀i ∈ J (a) z t -z i ≥ 0 ∀i ∈ J (b) z t ≤ M (c) z j -z i ≥ h j ∀i, j ∈ J, i ≺ j (d) z j ≥ 0 ∀j ∈ J (e) h j ≤ 1 ∀j ∈ J (f) h j ≥ 0 ∀j ∈ J (g) Proof.
Let us prove that the linear relaxation of (Dom) correponds to the polytope P from Theorem 3. For (U-AnchRob) for every i, j ∈ J such that i ≺ j we have L 0 ij = 0 since p = 0. The worst-case longest paths values are as follows. For every j ∈ J, L ∆ sj = 0 if j has no predecessor except s, and L ∆ sj = 1 otherwise. For every i ≺ j with i = s, L ∆ ij = 1. For a pair i ≺ j with i = s, inequality (3) thus writes z j -z i ≥ h j , which is inequality (d) or (b) from the definition of P. For a pair s ≺ j, inequality (3) writes z j -z s ≥ 0 if j has no predecessor in J, and z j -z s ≥ h j otherwise. If j has no predecessor in J, it is inequality (a) from the definition of P. Otherwise j has a predecessor k ∈ J and inequality z j -z s ≥ h j is dominated by inequalities z k -z s ≥ 0 and z j -z k ≥ h k . Hence it is satisfied by any element of P. Thus P Dom = P.

By Theorem 3, P is integer, hence Proj h (P) is integer. Namely, each extreme point of Proj h (P) is the incidence vector of an anchored set. Thus Proj h (P Dom ) = Proj h (P) = Q, and (Dom) yields a polyhedral characterization for the problem.

Note that Proposition 5 implies also the integrality of schedule variables z, which are not required to be integer in general.

As a corollary, a complexity result is that Theorem 3 generalizes the polynomial case of (U-AnchRob) proven in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF] for unit anchoring weights, to any non-negative anchoring weights.

The polyhedral characterization from (Dom) can be projected out to obtain a complete description of Q using h variables only. Namely, the inequalities from the projection stated in Proposition 3 are i∈C h i ≤ M for every chain C of the subposet (J * , ≺), where J * is the set of jobs with at least a predecessor different from s. It is a family of inequalities with exponential size. In that regard, (Dom) is a compact extended formulation with additional variables z: with O(n) continuous additional variables, it is possible to describe the polytope Q with a polynomial O(n 2 ) number of inequalities.

Critical precedence graphs

Let us now consider processing times p ∈ R J + . Recall that the precedence graph G(p) is critical if the length of all s-t paths is the same. A case where G(p) is critical is when processing times are equal to zero, since the length of all s-t paths is zero. For non-zero processing times, it can also be proven that for some precedence graphs, if G(p) is quasi-critical then it is critical. This holds for series-parallel precedence graphs; the result is proven in A and used for numerical results in Section 5 to generate critical precedence graphs.

Let us now consider a critical precedence graph G(p), and extend the polyhedral characterization result obtained in Section 4.2.1. It is assumed that M = L 0 st + δ 0 M with M integer. Indeed M can be tightened to L 0 st + δ 0 (M -L 0 st )/ δ 0 w.l.o.g. Under this assumption we prove that Theorem 4. For 1-disruption uncertainty and critical precedence graph, formulation (Dom) yields a polyhedral characterization of (AnchRob).

Proof. Let I denote an instance of (AnchRob) for 1-disruption uncertainty with deviation δ 0 , critical precedence graph G(p), and deadline M . Let z * be the earliest schedule of G(p), namely

z * i = L 0 si for every i ∈ J. Since G(p) is critical, for every i ≺ j it holds that L 0 si + L 0 ij + L 0 jt = L 0 sj + L 0 jt , hence L 0 ij = z * j -z * i . Also L ∆ ij = z * j -z * i + δ 0 . Inequalities (3) then write z j -z i ≥ (z * j -z * i ) + δ 0 h j , or equivalently zj -z * j δ0 - zi-z * i δ0 ≥ h j . Similarly the deadline constraint is equivalent to zt-z * t δ0 ≤ M -z * t δ0
. Consider a new instance I of (U-AnchRob) defined by: the precedence graph G, zero processing times, and

M = M -L 0 st δ0
. Then M is integer by assumption on M . Solution (z, h) is feasible for (Dom) in instance I if and only if solution ( z-z * δ0 , h) is feasible for (Dom) in instance I . Hence if (z, h) is an extreme point of P Dom then ( z-z * δ0 , h) is extreme for the (U-AnchRob) instance. By Proposition 5, vector h is integer. Hence the claimed result.

Theorem 4 thus yields a polyhedral characterization of polynomial size for this special case. We mention that this is a polynomial case of (AnchRob) that was not identified in [START_REF] Bendotti | The Anchor-Robust Project Scheduling Problem[END_REF].

Numerical results

We investigate the impact of theoretical polyhedral results from Section 4 on the performance of formulations (Lay), (Std), (Dom) for various instance classes. In Section 5.1, instances and settings are presented. Section 5.2 is dedicated to budgeted uncertainty, and Section 5.3 to partition-budgeted and mixed-budgeted uncertainty sets.

Instances and settings

Instances are randomly generated as follows. We consider instance classes with a four-field label F1 F2 F3 F4:

• Field F1 concerns precedence graph G -ER: precedence graphs randomly generated according to Erdos-Renyi model, i.e., arc (i, j) is in G with probability pr = 10/n.

-SP: Series-Parallel precedence graphs, inductively generated by drawing randomly series or parallel compositions.

• Field F2 denotes processing times p -pZero: p i = 0 for every i ∈ J;

-pRand: p i is randomly generated in range [5,20];

-pQCri: p is obtained by applying the following procedure: start from the values generated for class pRand; increase the processing time of a randomly selected job until every job is on a critical path. Hence G(p) is quasi-critical.

• Field F3 denotes deviation δ -dRand: for instances pRand and pQCri, δ i is randomly generated in [1, 1 2 p i ] for every i ∈ J; for instances pZero, δ is equal to the values generated for instances pQCri;

-dUnif: δ i = δ 0 for every i ∈ J. Value δ 0 is randomly selected in the deviation values of instances dRand.

• Field F4 denotes the uncertainty set -Γ1, Γ2, Γ3 correspond to budgeted uncertainty with deviation defined by F3 and Γ = 1, 2, 3 respectively.

-Partition: jobs are partitioned into two subsets J 1 and J 2 , every job being in J 1 with probability 0.75. Given the deviation δ defined by F3, the deviation vector of the Partition instance is 0.1 δ i for every i ∈ J 1 , and δ i for every i ∈ J 2 . Budgets are Γ 1 = 10 and Γ 2 = 1.

-Mixed: ∆ = ∆ 1 ∪ ∆ 2 where ∆ 1 has deviation δ defined by F3 and Γ 1 = 1, and ∆ 2 has deviation τ δ, with τ = 0.2 and δ defined by F3 and Γ 2 = 10.

Each label corresponds to a class of 10 instances. For completeness, a formal definition of series-parallel precedence graphs is given in A. It is also proven in the Appendix that instance classes SP pQCri yield critical precedence graphs.

The number of jobs is set to n = 300. Anchoring weights are unitary. Deadline M is set to

M 1 2 = 1 2 (L G(p) (s, t) + L G(p+ δ) (s, t))
, that is, it is halfway between the min makespan of any schedule of G(p) and the min makespan of a static-robust schedule. Unreported results showed that choosing a deadline other than M 1 2 leads to similar results in terms of the comparison of formulations. For budgeted uncertainty, the budget is Γ ∈ {1, 2, 3}. The choice of a small uncertainty budget was previously motivated in the literature, see, e.g., [Bendotti et al., 2019, Herroelen and[START_REF] Herroelen | The construction of stable project baseline schedules[END_REF].

For each instance, formulations (Dom), (Std), and (Lay) have been implemented using Julia 0.6.2, JuMP 0.18.5. Mixed-integer programs are solved with CPLEX 12.8 on a PC under Windows 10 with Intel Core i7-7500U CPU 2.90GHz and 8 Go RAM. The time limit is 300 seconds.

The valid inequalities (4) appear to be added by CPLEX on the fly. Thus they are not hardcoded in formulations.

Impact of instance parameters for budgeted uncertainty

Let us first investigate the case of budgeted uncertainty. Table 1 andTable 2 present the results for ER and SP instances respectively. Each table presents results relative to 8 instance classes: the first 6 instance classes are with Γ = 1 and with all combinations of processing times and deviations, and the last 2 instance classes are with Γ = 2 and Γ = 3. For each instance class, checkmarks in the first three columns indicate if the assumptions of Theorem 4 are matched:

-crit.: the precedence graph G(p) is critical; -unif.: deviation δ is uniform; -Γ1: Γ = 1. The tables feature:

-opt: average optimal value for instances solved optimally; -for each formulation (Lay), (Std) and (Dom):

-#solved: number of instances, out of 10, solved optimally within the time limit; -gap: average final gap of unsolved instances; -time: average computation time for solved instances in seconds; -LPGap: average gap b-opt opt between integer optimum opt and linear bound b; -CPXGap: average gap obtained by CPLEX at root node.

The computation times do not include the preprocessing time for computing L ∆ ij values. The computation is done by a dynamic programming algorithm linear in Γ|A|. Its running time is negligible with respect to MIP computation time: on average 0.153 seconds for ER instances and 0.161 seconds for SP instances.

Let us now comment on the impact of the instance parameters.

Polyhedral characterization cases. Instance classes ER pZero dUnif Γ1, SP pZero dUnif Γ1, and SP pQCri dUnif Γ1, correspond to polyhedral characterization cases. As expected, formulation (Dom) solves the problem in less than one second and LPGap = 0%. Formulation (Lay) has non-zero LPGap, but CPLEX adds suitable cuts to close the gap at root node.

Impact of uniform deviation. Consider now the 6 instance classes F1 F2 dUnif Γ1. These are the first three row entries of Table 1 and the first three row entries of Table 2. On these 6 instance classes, formulations (Dom) and (Lay) still behave well. (Dom) solves all instances in less than one second. In particular, its LPGap is still very small: at most 0.42%. (Lay) also performs well, the LPGap of (Lay) is larger, but CPXGap is comparable for (Dom) and (Lay). We note that uniform deviation has an important impact on the performance of formulations. Consider, e.g., instance classes SP pZero dUnif Γ1 and SP pZero dRand Γ1. For uniform deviation (Dom) is integer ; for non-uniform deviation it has 9.70% CPXGap and solves only 4 instances out of 10 within the time limit. By contrast with (Dom) and (Lay) on these instances, formulation (Std) performs very poorly and solves only 41 instances out of 120 (vs. 107 out of 120 for (Dom)).

Impact of the precedence graph. The impact of the precedence graph being critical is limited, as shown for example by the comparison of instances ER pZero and ER pQCri. Both are efficiently solved, while the precedence graph is critical for the former, and not critical for the latter. Even more, instances with pRand appear to be easy instances, while they do not have critical precedence graphs. An interpretation is that for such instances, a large number of jobs are not on critical paths and thus they can be anchored; note, e.g., that the optimal value is greater for pRand instances than for others.

Impact of uncertainty budget. When Γ is increased, the performance of (Lay) deteriorates. It gets even worse than (Std) for ER instances, see ER pZero dUnif Γ3 where (Std) solves 3 instances and (Lay) solves 1 instance. Importantly, the size of formulation (Lay) increases with Γ. For (Dom) and (Std) only the values of the coefficients L ∆ ij depend on the budget, and not the size of the formulation.

Beyond budgeted uncertainty

Let us now present results when ∆ is an uncertainty set with several budgets.

Partition-budgeted uncertainty set

Table 3 and Table 4 give computational results for ER and SP instances under Partition uncertainty. In this case, the L ∆ ij values were computed by a dynamic programming algorithm with complexity linear in Γ 1 Γ 2 |A|. The computation was done in 4.364 seconds on average for ER instances, and 4.916 seconds on average for SP instances.

It comes that (Dom) solves all 60 ER instances, and 54 SP instances, which is better than for budgeted uncertainty. For SP instances, the results are comparable to those of budgeted uncertainty. By contrast, ER instances appear to be very easy for this uncertainty set. Hence solving the MIP formulation (Dom) for Partition uncertainty does not seem harder than for budget Γ1. This highlight that (Dom) can be readily used to handle several budget constraints. In this case ∆ = ∆ 1 ∪ ∆ 2 where ∆ 1 is the uncertainty set corresponding to instance classes with fourth field Γ1. The L ∆ ij values were precomputed by the same dynamic programming algorithm as for budgeted uncertainty. This computation was done in 0.152 seconds on average for ER instances, and seconds on average for SP instances.

First, (Dom) solves optimally 59 ER instances and 42 SP instances for Mixed, in comparison with 59 ER instances and 48 SP instances for budgeted uncertainty (Γ = 1). That is, the performance of the formulation is not very sensitive to the change of uncertainty set. Some conclusions given in Section 5.2 also hold for Mixed uncertainty. Namely, instances with dUnif are easier than instances with dRand. It can be related to the influence of uniform deviation on the performance of (Dom), in connection with the polyhedral characterization result.

The optimal number of anchored jobs is often the same for ∆ or ∆ 1 . Namely, the value of opt can be compared between Table 1 and Table 5 for ER instances, and between Table 2 and Table 6 for SP instances. For example for instance classes SP pZero dRand Γ1 and SP pZero dRand Mixed the average optimal value is equal to 247.00, hence all instances have the same optimal value for uncertainty set ∆ and ∆ 1 . This means that the uncertainty set can be extended from ∆ 1 to ∆ = ∆ 1 ∪ ∆ 2 without deteriorating the number of anchored jobs.

Conclusion on numerical experiments

In the numerical experiments, we evaluated the performance of formulations for budgeted uncertainty sets, and uncertainty sets obtained by union or intersection of budgeted uncertainty sets. For budgeted uncertainty sets, numerical tests showed that (Dom) outperforms the previously known formulation (Lay), that was dedicated to budgeted uncertainty. An advantage of formulation (Dom) over (Lay) is that the size of (Dom) is independent of the budget Γ, while (Lay) has O(nΓ) variables.

We then investigated the impact of the parameters on the performance of (Dom). The influence of uniform deviation and small uncertainty budget is important, while the impact of critical precedence graphs is not significant on the efficiency of the formulation. Interestingly (Dom) is efficient for instances that are not matching the polyhedral characterization case, but where deviation δ is uniform and Γ is small.

The proposed approach is to precompute the L ∆ ij values, then solve the obtained MIP formulation. This allowed us to solve the problem for a variety of uncertainty sets for which no linear formulation was previously investigated. The precomputing time remains small (at most 5 seconds for partition-budgeted uncertainty sets) on the considered instances, and the MIP computation time for (Dom) is comparable to that under budgeted uncertainty. While it was expected that (Dom) would outperform standard linearization (Std), the computational interest of applying the dominance is highlighted by the number of solved instances: on a total number of 400 instances, 358 are solved by (Dom), only 191 by (Std).

Conclusion

In the present work we investigated a versatile mixed-integer programming approach for the (AnchRob) problem. This led to a linear formulation that is applicable to any uncertainty set, provided that an algorithm for precomputing the worst-case longest paths values is available. This widens the range of uncertainty sets for which MIP formulations for (AnchRob) are known. The keypoint for establishing a strong MIP formulation is the analysis of the combinatorial properties of (AnchRob), among which a dominance property. This property allows for a characterization of the anchored sets polytope in interesting special cases. The theoretical positive results for the dominance-based formulation also go together with good numerical performances around the polyhedral characterization case, for both budgeted uncertainty and uncertainty sets with several budgets.

An interesting research direction is to benefit from the obtained polyhedral results to solve large-scale instances. Another direction is to extend these results and tackle project scheduling under resource constraints. Resource constraints are indeed very salient in applications. It is worth investigating how anchored jobs may interfere with resource constraints, and see whether dominance may help again in the design of efficient linear formulations. Another perspective is to identify other problems where an anchor-robust counterpart could be defined, and solved efficiently with mixed-integer programming.

A Series-parallel precedence graphs

Series-parallel digraphs are defined recursively as follows. A digraph is series-parallel with terminals s and t if one of the three assertions is satisfied:

• Its vertex-set is {s, t} and its arc-set is {(s, t)};

• (Series composition.) It is formed with two series-parallel digraphs G 1 and G 2 , where terminals t 1 and s 2 have been identified;

• (Parallel composition.) It is formed with two series-parallel digraphs G 1 and G 2 , where the two pairs of terminals s 1 and s 2 , and t 1 and t 2 , have been identified. We assume that G 1 and G 2 have strictly more than 2 vertices.

Series-parallel precedence graphs are series-parallel digraphs with terminals the dummy jobs s and t.

Proposition 6. If G is series-parallel and G(p) is quasi-critical, then G(p) is critical.

Proof. If G is a path, then G(p) is critical. If G is obtained by series composition of G 1 and G 2 ; then any s-t path is formed by an s 1 -t 1 path in G 1 and an s 2 -t 2 path in G 2 . Hence if G 1 and G 2 are critical, it follows that G is critical. If G is obtained by parallel composition of G 1 and G 2 , both critical, let i ∈ G 1 and j ∈ G 2 . Then every s-t path going through G 1 (resp.

G 2 ) has length L G 1 (s, t) = L G 1 (s, i) + L G 1 (i, t) (resp. L G 2 (s, t) = L G 2 (s, j) + L G 2 (j, t)). If G is quasi-critical, L G (s, i) + L G (i, t) = L G (s, j) + L G (j, t), and it follows that all s-t paths of G have same length.

Figure 1 :

 1 Figure 1: Precedence graph for an instance with 5 jobs, with arc-weights p + δ.

Figure 2 :

 2 Figure 2: Schedule x = (0, 1, 1, 3, 2.5) and set H = {1, 2, 4} in dark gray, x-anchored for box uncertainty set ∆ = Π i∈J [0, δ i ].

Figure 3 :

 3 Figure3: Schedule x = (0, 1, 1, 3, 2.5) and set H = {1, 2, 4, 5} in dark gray, x-anchored for budgeted uncertainty set ∆ = {( δ i u i ) i∈J : u ∈ {0, 1} J , i∈J u i ≤ 1}.

  is exactly the set of schedules of G H with makespan at most M . Let z be the earliest schedule of G H . By assumption, there exists a schedule in X ≤M (H), thus z t ≤ M . Let i ∈ J ∪ {s} and j ∈ H. Let us show that z j -z i ≥ L ∆

ij holds, even for i / ∈ H ∪ {s}. Consider a longest s-i path P * si in G H , and let k ∈ H ∪ {s} be the last vertex of H ∪ {s} on this path. Then z

Table 1 :

 1 ER instances, budgeted uncertainty

	instance	crit. unif. Γ1	opt		#solved	gap time(s) LPGap CPXGap
	ER pZero dUnif Γ1		271.90	(Lay)	10	-	1	9.20%	0.90%
				(Std)	1	1.19%	144	5.14%	3.07%
				(Dom)	10	-	<1	0%	0%
	ER pQCri dUnif Γ1		274.30	(Lay)	10	-	26	8.39%	0.87%
				(Std)	0	2.05%	-	8.04%	4.29%
				(Dom)	10	-	1	0.42%	0.24%
	ER pRand dUnif Γ1		290.40	(Lay)	10	-	<1	3.06%	0.06%
				(Std)	10	-	30	3.02%	1.62%
				(Dom)	10	-	<1	0.10%	0%
	ER pZero dRand Γ1		214.77	(Lay)	9	2.84%	21	34.15%	7.93%
				(Std)	9	4.92%	65	28.53%	4.68%
				(Dom)	9	1.81%	11	21.13%	3.28%
	ER pQCri dRand Γ1		225.80	(Lay)	8	0.98%	21	28.54%	7.70%
				(Std)	6	2.30%	41	30.25%	5.41%
				(Dom)	10	-	31	18.09%	3.69%
	ER pRand dRand Γ1		290.20	(Lay)	10	-	<1	3.00%	0.36%
				(Std)	10	-	<1	3.02%	1.74%
				(Dom)	10	-	<1	0.82%	0.07%
	ER pZero dUnif Γ2		255.50	(Lay)	2	1.88%	113	15.11%	9.93%
				(Std)	1	4.20%	237	10.93%	7.58%
				(Dom)	10	-	53	3.91%	2.46%
	ER pZero dUnif Γ3		243.50	(Lay)	1	4.41%	111	19.77%	13.69%
				(Std)	3	5.48%	153	15.76%	7.78%
				(Dom)	10	-	105	7.18%	3.51%
	instance	crit. unif. Γ1	opt		#solved	gap time(s) LPGap CPXGap
	SP pZero dUnif Γ1		255.90	(Lay)	10	-	<1	17.09%	0%
				(Std)	0	3.34%	-	8.64%	6.81%
				(Dom)	10	-	<1	0%	0%
	SP pQCri dUnif Γ1		255.90	(Lay)	10	-	<1	17.09%	0%
				(Std)	0	6.88%	-	14.82%	8.96%
				(Dom)	10	-	<1	0%	0%
	SP pRand dUnif Γ1		262.80	(Lay)	10	-	<1	14.19%	0.42%
				(Std)	0	6.86%	-	13.36%	7.29%
				(Dom)	10	-	<1	0.05%	0%
	SP pZero dRand Γ1		247.00	(Lay)	4	3.72%	3	32.46%	16.43%
				(Std)	2	18.60%	11	25.97%	20.07%
				(Dom)	4	9.12%	15	16.42%	9.70%
	SP pQCri dRand Γ1		247.00	(Lay)	4	3.52%	3	32.38%	16.72%
				(Std)	2	23.58%	30	35.21%	27.94%
				(Dom)	4	9.83%	14	16.54%	9.90%
	SP pRand dRand Γ1		268.60	(Lay)	10	-	3	11.51%	6.97%
				(Std)	1	6.09%	193	11.05%	9.34%
				(Dom)	10	-	16	2.26%	0.92%
	SP pQCri dUnif Γ2		246.66	(Lay)	7	0.85%	45	22.65%	10.58%
				(Std)	0	11.80%	-	20.92%	16.63%
				(Dom)	9	0.77%	31	2.44%	1.35%
	SP pQCri dUnif Γ3		246.14	(Lay)	5	2.77%	57	26.40%	16.38%
				(Std)	1	17.42%	215	25.47%	20.68%
				(Dom)	7	2.19%	38	3.92%	3.29%

Table 2 :

 2 SP instances, budgeted uncertainty

Table 3 :

 3 ER instances, Partition uncertainty

	instance	crit. unif. Γ1	opt		#solved	gap time(s) LPGap CPXGap
	SP pZero dUnif Partition		274.70	(Lay)	-	-	-	-	-
				(Std)	8	1.36%	14	4.48%	2.01%
				(Dom)	10	-	<1	0%	0%
	SP pQCri dUnif Partition		273.44	(Lay)	-	-	-	-	-
				(Std)	4	7.42%	43	10.57%	8.29%
				(Dom)	9	3.22%	14	1.43%	0.84%
	SP pRand dUnif Partition		284.90	(Lay)	-	-	-	-	-
				(Std)	8	2.12%	57	4.89%	2.71%
				(Dom)	10	-	<1	0.17%	0%
	SP pZero dRand Partition		246.87	(Lay)	-	-	-	-	-
				(Std)	7	11.40%	1	23.12%	4.54%
				(Dom)	8	4.05%	33	19.43%	2.79%
	SP pQCri dRand Partition		247.42	(Lay)	-	-	-	-	-
				(Std)	7	13.46%	1	27.36%	5.16%
				(Dom)	7	3.28%	<1	19.33%	2.66%
	SP pRand dRand Partition		279.10	(Lay)	-	-	-	-	-
				(Std)	7	4.89%	44	7.10%	5.05%
				(Dom)	10	-	1	1.85%	0.41%

Table 4 :

 4 SP instances, Partition uncertainty 20 5.3.2 Mixed-budgeted uncertainty setsTable 5 and Table 6 give computational results for ER and SP instances under Mixed uncertainty.

Table 5 :

 5 ER instances, Mixed uncertainty

	instance	crit. unif. Γ1	opt		#solved	gap time(s) LPGap CPXGap
	SP pZero dUnif Mixed		255.70	(Lay)	-	-	-	-	-
				(Std)	0	3.60%	-	8.72%	6.84%
				(Dom)	10	-	1	0.06%	0%
	SP pQCri dUnif Mixed		246.75	(Lay)	-	-	-	-	-
				(Std)	2	24.10%	37	35.77%	24.48%
				(Dom)	4	10.15%	13	16.59%	9.99%
	SP pRand dUnif Mixed		262.80	(Lay)	-	-	-	-	-
				(Std)	0	6.74%	-	13.36%	7.64%
				(Dom)	10	-	1	0.05%	0%
	SP pZero dRand Mixed		247.00	(Lay)	-	-	-	-	-
				(Std)	2	19.25%	16	26.63%	19.47%
				(Dom)	4	9.43%	13	16.40%	10.19%
	SP pQCri dRand Mixed		247.00	(Lay)	-	-	-	-	-
				(Std)	2	23.86%	30	35.52%	25.37%
				(Dom)	4	9.15%	12	16.26%	10.19%
	SP pRand dRand Mixed		268.40	(Lay)	-	-	-	-	-
				(Std)	1	6.03%	179	11.00%	9.48%
				(Dom)	10	-	26	2.34%	1.08%

Table 6 :

 6 SP instances, Mixed uncertainty

and let P = {(z, h) ∈ R J × R J : (a) -(g)}.

Theorem 3. The polytope P is integer.

Proof. Consider the polytope P formed with all pairs (z, h) ∈ R J + ×R J + satisfying the constraints (a)-(g). To prove integrality of P, the main idea is to define an auxiliary extended polyhedron where h variables can be expressed linearly from z variables and additional z variables. Let us define the auxiliary polyhedron P formed with all triplets (z, z , h

Let us prove the following claim. Claim 1. P = Proj z,h (P ). First, given (z, h) ∈ P, let us prove the existence of z such that (z, z , h) ∈ P . Define z j = 1 + z j -h j for every j ∈ J, and z s = z s , z t = 1 + z t . Then the (in)equalities (i) to (vii) can be checked for the triplet (z, z , h) as follows.

-(i) and (vi) hold by assumption on z, and (vii) by definition of z ;

Conversely, let (z, z , h) ∈ P . Let us check inequalities (a)-(g) for (z, h).

-(a) holds by sum of (i) along an s-i path; -(b) holds by sum of (i) along an i-t path; -(c) is clear; -(d): for i ≺ j we have z j -z i = z j -z j +z j -z k +z k -z i , where k is the last vertex distinct from j on a path from i to j in the precedence graph (possibly k = i). Then (k, j) ∈ A so z j -z k ≥ 1 by (iii). Also z k -z i ≥ 0 by summing (i) along the i-k path. Hence z j -z i ≥ z j -z j +1+0 = h j by (vii). Hence (d) is satisfied; -(f) (resp. (g)) comes from (vii) and (iv) (resp. (vii) and (v)). This completes the proof of Claim 1. Now we prove: Claim 2. P is integer. Let (z, z , h) be an extreme point of P . It satisfies the n equalities (vii) and it saturates 2(n + 2) linearly independent inequalities among (i)-(vi). Thus (z, z ) is an extreme point of {(z, z ) ∈ R J + × R J + : (i)-(vi)}. The constraint matrix of (i)-(vi) is totally unimodular, and the right-hand side is integer since M is integer. Hence (z, z ) is integer and so is (z, z , h). This ends the proof of Claim 2.

By Claim 1, P = Proj z,h (P ). It holds that for any extreme point (z, h) of P there exists z such that (z, z , h) is an extreme point of P . By Claim 2, such (z, z , h) is integer, hence (z, h) is integer. This proves the integrality of P.

Theorem 3 implies the following polyhedral characterization Proposition 5. Formulation (Dom) yields a polyhedral characterization for (U-AnchRob).