Virginie Gabrel
email: gabrel@lamsade.dauphine.fr

Cécile Murat
email: murat@lamsade.dauphine.fr

Robust shortest path problems

Keywords: plus court chemin, optimisation robuste, incertitudes sur les données, scénario du pire cas, regret maximum shortest path, robust optimization, data uncertainties, worst case scenario, maximal regret

Cet article constitue un état de l'art sur les problèmes de plus courts chemins pour lesquels il existe des éléments d'incertitude et d'indétermination sur les valeurs des arcs. Deux modèles d'incertitude sont distingués : celui dit par intervalle et celui dit par scénarios. Différentes mesures et approches de la robustesse sont présentées : celles issues de la théorie de la décison, celles issues de l'analyse multicritère et celles issues de la programmation mathématique. Elles donnent lieu à plusieurs versions distinctes du problème de plus court chemin robuste dont les complexités et les résolutions sont présentées.

Introduction

In optimization, it is used to deal with uncertain and inaccurate factors which make difficult the assignment of a single plausible value to each model parameters. Two approaches are possible : in the first one, a single nominal value is assigned to each parameter, the corresponding optimal solution is computed, then the interval in which each parameter can vary in order to preserve optimality solution is determined ; the second approach consists in taking into account in the model to optimize, the possible variations of each parameter. In mathematical programming, the first approach is known as sensibility analysis. For the second approach, stochastic optimization may be applied for some problems in which parameters' value can be described by probability laws. When it is not possible nor relevant to associate probability laws to parameters, another way amounts to assign a set of possible values to each parameter. In this context, the choice of one value in each set corresponds to a scenario. The induced robust optimization problem is to determine a single solution which is optimal for all scenarios. In general, such a solution does not exist and the problem is to determine a "relatively good" solution for all scenarios.

In most of robustness studies in combinatorial optimization, a robust solution is a solution which is acceptable in a large majority of scenarios and, which is never too bad (cf for example [START_REF] Roy | Flexibilité et Robustesse en Ordonnancement, chapter A propos de robustesse en recherche Opérationnelle et Aide à la Décision[END_REF][START_REF] Vincke | Robust solutions and methods in decision-aid[END_REF]). This characterization leaves place to many possible interpretations and, thus gives place to various approaches of robustness. These approaches differ from models used to represent the uncertain and inaccurate factors of the considered decision problem, from methodology used to measure robustness, and finally from the analysis and the design of resolution methods.

In this chapter, we present various models, criteria and methods which were studied for the robust shortest path problem. In the section 2, models are proposed then comes in the section 3, the presentation of different measures of robustness, and finally, in the parts 4 and 5, is presented complexities and resolutions of various versions of the robust shortest path problem.

Models for representing uncertain, undetermined and random factors

We consider a directed valued graph G = (X, U ) such as X = {1, . . . , n} and |U | = m. A path µ from 1 to n in G is a sequence of arcs : µ = {(i 0 = 1, i 1 ), (i 1 , i 2 ), . . . , (i k-1 , i k = n)}. Within the deterministic framework, to each arc u = (i, j) ∈ U is associated a single value c u = c ij . The value of µ is then given by : c(µ) = (i,j)∈µ c ij . A traditional problem of combinatorial optimization consists in determining the shortest path, denoted by µ * G , among the set C of paths from 1 to n in G.

When elements of uncertainty and/or inaccuracy must be taken into account, it can be no more relevant, even possible, to set a single value c ij for each arc (i, j).

In some contexts, these values are described by probability laws. The problem then becomes the stochastic shortest path problem that we will not study in this paper.

In other contexts, uncertain, inaccurate and random factors cannot be efficiently modeled by probability laws. Since the middle of the 90', two models were more particularly developed in the literature : the so-called interval model and the discrete set of scenarios model. In these two models, each arc is associated with a set of values, this set may be of infinite or finite size. The assumption is that on each arc, the real value belongs to its associated set. A scenario corresponds to the specification of a single value for each arc. We will note S the set of q relevant scenarios, c s ij the value of arc (i, j) under scenario s, c s (µ) the value of path µ under scenario s, G s the graph valued according to the scenario s, µ * G s the shortest path from 1 to n in G s .

In the two next sections, we present the so-called interval model and the so-called discrete set of scenarios model. EXAMPLE. Let us consider the path µ = (1, 2, 4, 5, 7) in the graph G of the figure 1 whose arcs are valued by intervals. Under any scenario s, this path has a value c s (µ) belonging to the interval [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Spanjaard | Exploitation de préférences non-classiques dans les problèmes combinatoires : modèles et algorithmes pour les graphes[END_REF]. This model is considered for the shortest path problem in [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Karaşan | The robust shortest path problem with interval data[END_REF][START_REF] Kasperski | The robust shortest path problem in series-parallel multidigraphs with interval data[END_REF][START_REF] Montemanni | An exact algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Montemanni | The robust path problem with interval data via benders decomposition[END_REF][START_REF] Zieliński | The computational complexity of the relative robust shortest path problem with interval data[END_REF].

The interval model

In addition, the interval model is applied to other combinatorial problems, for example the minimum spanning tree [START_REF] Montemanni | A benders decomposition approach for the robust spanning tree problem with interval data[END_REF][START_REF] Yaman | The robust spanning tree problem with interval data[END_REF], the problem of selecting p elements among n with minimal total weight [START_REF] Averbakh | On the complexity of a class of combinatorial optimization problems with uncertainty[END_REF], or the assignment problem [START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF].

The discrete set of scenarios model

In the discrete set of scenarios model, a finite set S of scenarios is considered. Thus, given q scenarios, each arc (i, j) is associated to a finite set of q plausible values {c 1 ij , . . . , c q ij }.

[2, 7]

[1, 7] [1, 4] [1, 10] [1, 2] [1, 2] [1, 7] [1, 10] [1, 9] [1, 9]

FIG. 1 -Example of interval model

Let us note that on the contrary of interval model, any combination of values c ij does not constitute a relevant scenario. Consequently, each path µ is associated to a q dimension vector V (µ) such as V (µ) = (c 1 (µ), . . . , c q (µ)), where c s (µ) = (i,j)∈µ c s ij with s ∈ {1, . . . , q}.

EXAMPLE. Let us consider the graph G of the figure 2 whose arcs are valued according to three scenarios. This model is considered for the shortest path problem in [START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF][START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF][START_REF] Spanjaard | Exploitation de préférences non-classiques dans les problèmes combinatoires : modèles et algorithmes pour les graphes[END_REF][START_REF] Yu | On the robust shortest path problem[END_REF].

In addition, the discrete set of scenarios model is applied to other combinatorial problems, for example the minimum spanning tree in [START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF][START_REF] Spanjaard | Exploitation de préférences non-classiques dans les problèmes combinatoires : modèles et algorithmes pour les graphes[END_REF], the problem of selecting p elements among n with minimal total weight in [START_REF] Averbakh | On the complexity of a class of combinatorial optimization problems with uncertainty[END_REF], the 1-median location problem in TAB. 1 -Elementary paths from 1 to 7 [START_REF] Kalai | Robust 1-median location problem on a tree[END_REF][START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF], or the assignment problem [START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF][START_REF] Deȋneko | On the robust assignment problem under a fixed number of cost scenarios[END_REF].

µ c 1 (µ) c 2 (µ) c 3 (µ) µ 1 = (1,
A more general model is presented in [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF] which includes the two previous models. In this general framework, arcs value are determined by a set of r parameters. These parameters are not exactly known and two models are considered : a discrete set of parameters r-tuples, and a continuous subset of R r delimited by constraints (for which the interval model is a particular case).

Robustness measures

In this section, we list models to evaluate a path in term of robustness. Three approaches can be distinguished : the first one, coming from the decision theory, models the concept of robustness through a single criterion to be optimized ; the second one uses the mathematical programming to address data uncertainty ; and the third one, coming from the multicriteria analysis and the social choice theory, attempts to characterize the robust solutions by a set of conditions to be checked.

Classical criteria resulting from the decision theory

Worst case criterion

Given a path, the scenario to be considered is the one that gives the worst value for this path. In this context, the value of a path µ, noted v WOR (µ), is defined by :

v WOR (µ) = max s∈S c s (µ)
EXAMPLE. Let us consider the path µ = (1, 2, 4, 5, 7) of the graph in the figure 1. The worst case scenario is the one for which each arc value is equal to its upper bound. In this case, v WOR (µ) = 24.

The problem is to determine the path µ * WOR which minimizes v WOR as follows :

v WOR (µ * WOR ) = min µ∈C v WOR (µ)
Under any scenario s ∈ S, µ * WOR has a value lower or equal to v WOR (µ * WOR ). Thus, v WOR (µ * WOR ) can be considered as an upper bound which offers an absolute guarantee. That is why in the work of Kouvelis and Yu [START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF], solutions which optimize this criterion are called absolute robust solutions. In decision theory, this criterion models the behavior of a decision maker averse to risk.

The maximum regret criterion

Given a scenario s, the choice of a path µ which is not necessarily a shortest path in G s , generates a regret denoted r s (µ) = c s (µ) -c s (µ * G s ). A path µ is then evaluated by v REG (µ) on the basis of the maximum regret scenario : The optimal solution according to the maximum regret criterion will be denoted µ * REG and checks :

v REG (µ) = max
v REG (µ * REG ) = min µ∈C v REG (µ)
EXAMPLE. Let us consider again the graph in the figure 2 for which three scenarios are taking into account. Since the shortest path in each scenario is respectively

µ * G 1 = (1, 2, 4, 5, 7) of value 6, µ * G 2 = (1, 2, 6, 7) of value 4 and µ * G 3 = (1, 3, 2, 6, 7
) of value 5, we can determine the values v WOR (µ) and v REG (µ) for any path µ, presented in the table 2.

Optimal solutions according to the worst case criterion are paths µ 2 and µ 4 , and the optimal solution according to the maximum regret criterion is the path µ 8 .

In the work of Kouvelis and Yu [START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF], a solution which optimizes the maximum regret criterion is called a robust deviation solution. In addition, they propose another criterion of

µ v WOR (µ) v REG (µ) µ 1 = (1, 2, 6, 7) 19
v REG ′ (µ) = max s∈S c s (µ) -c s (µ * G s ) c s (µ * G s )
This criterion must also be minimized.

Classical criteria coming from decision theory evaluate solutions on the basis of extreme scenarios. The major disadvantage is to focus on a single scenario, mainly the worst case, without taking into account all others scenarios. On the other hand, these criteria offer optimality guarantees. In particular, Averbakh in [START_REF] Averbakh | Minmax regret solutions for minimax optimization problems with uncertainty[END_REF] proposes a very lighting interpretation of the maximum regret criterion. He supposes, rather naturally, that a solution is robust if it is a good solution on all the scenarios. Thus, for a scenario s, robust solutions must belong to the set, denoted C s ǫ , of the ǫ-optimal solutions verifying :

c s (µ) -c s (µ * G s ) ≤ ǫ.
The set, denoted C ROB ǫ , of robust solutions is then the intersection of all ǫ-optimal solutions sets, one per scenario, as follows :

C ROB ǫ = s∈S C s ǫ It is obvious that if ǫ is too small, C ROB
∀µ ∈ C ROB ǫ , ∀s ∈ S, c s (µ) -c s (µ * G s ) ≤ ǫ ⇒ ∀µ ∈ C ROB ǫ , max s∈S (c s (µ) -c s (µ * G s )) = v REG (µ) ≤ ǫ But, since ∀µ ∈ C ROB ǫ , v REG (µ) ≥ v REG (µ * REG ), if ǫ < v REG (µ * REG ) then C ROB ǫ
is empty, and otherwise, C ROB ǫ contains at least µ * REG . Consequently, v REG (µ * REG ) is the smallest ǫ such as it exists at least one solution which is ǫ-optimal for all scenarios. This interpretation may be adapted to the relative deviation criterion by modifying the definition of ǫ-optimal solution as follows : for a scenario s, µ is ǫ-optimal if and only if

c s (µ)-c s (µ * G s ) c s (µ * G s ) ≤ ǫ.

Methodology coming from mathematical programming

The shortest path problem can be represented by an integer linear program of the form :

(P)    min (i,j)∈U c ij y ij s.c y ∈ Y
In studies dealing with robustness in mathematical programming, we can distinguish those in which data uncertainty affects only the elements of the constraint matrix, and those in which data uncertainty concerns only objective function coefficients. In this context, a very interesting approach is introduced by Bertsimas and Sim (in [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF] and [START_REF] Bertsimas | The price of robustness[END_REF]). They consider the following interval model for objective function coefficients :

c ij ∈ [c ij , c ij + c ij ]
where c ij is the nominal value for (i, j) and c ij ≥ 0 represents the deviation from the nominal coefficient c ij . They start from the quite natural idea that the worst case will not happen simultaneously for all coefficients. In [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF], authors "stipulate that nature will be restricted in its behavior, in that only a subset of coefficients will change in order to adversely affect the solution". So, they introduce a parameter Γ which represents the maximum number of coefficients that can deviate from their nominal value : Γ = 0 means that none coefficient will vary, while Γ = m means that all coefficients will vary in the worst case sense. So, Γ is interpreted as a level of robustness.

The robust version of the shortest path problem becomes :

(P ROB )        min   (i,j)∈U c ij y ij + max {R|R⊆U,|R|≤Γ} (ij)∈R c ij y ij   s.c y ∈ Y

Methodology coming from multicriteria analysis

In multicriteria analysis [START_REF] Roy | Méthodologie multicritère d'aide à la décision[END_REF], a decision problem is commonly defined using a set of solutions, a discrete set of criteria and an aggregation model of these criteria. A solution is thus described by its evaluation vector containing the solution value on each criterion. Considering a scenario as a criterion, a part of the results obtained in multicriteria analysis can be used for the robustness analysis (cf [START_REF] Hites | About the applicability of mcda to some robustness problems[END_REF]). In this context, the robustness analysis is based upon the choice of an evaluation vector associated with each solution, and the definition of an aggregation model of these evaluation vectors.

Path evaluation vector

When the set of scenarios is discrete, it is natural to consider the vector V (µ), representing all possible values of µ on various scenarios, as an evaluation vector (cf [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF] and [START_REF] Hites | About the applicability of mcda to some robustness problems[END_REF]).

More recent work ( [START_REF] Kalai | Robust 1-median location problem on a tree[END_REF] and [START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF]) applies the anonymous principle which consists in admitting that the vector V (µ) = (c 1 (µ), . . . , c q (µ)) is equivalent to the vector V (µ) = (c σ(1) (µ), . . . , c σ(q) (µ)) for any permutation σ(i) of the q scenarios. According to this principle, a path µ can be evaluated by a vector obtained by ordering the values c i (µ) in a decreasing order. This vector is called disutility vector in [START_REF] Kalai | Robust 1-median location problem on a tree[END_REF], and is denoted D(µ) = (d 1 (µ), . . . , d q (µ)), where d 1 (µ) ≥ . . . ≥ d q (µ) with d i (µ) representing the value of order i of the path µ.

In some other studies on robustness, another so-called equity principle is proposed. According to this principle, a solution whose evaluations are well distributed around the average on the various scenarios is always preferred to a more unbalanced solution. For that, one evaluates a solution on the basis of the following vector, called in [START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF] the generalized Lorenz vector : L(µ) = (l 1 (µ), . . . , l q (µ)) with l j (µ) = j i=1 d i (µ).

EXAMPLE. For the graph in figure 2, desutility and generalized Lorenz vectors are presented for each path in the table 3. TAB. 3 -Evaluation vectors for paths from 1 to 7

Desutility vectors Lorenz vectors

µ d 1 (µ) d 2 (µ) d 3 (µ) l 1 (µ) l 2 (µ) l 3 (µ) µ 1 = (1,

Aggregation models for robustness

In multicriteria analysis, the dominance relation is defined as follows.

DEFINITION. Given a family F = (f 1 , . . . , f q ) of q criteria, a path µ dominates a path µ ′ if and only if f i (µ) ≤ f i (µ ′ ) for i = 1, . . . , q, with at least one strict inequality. The path µ ′ is then dominated by µ, that one notes µ∆ F µ ′ .

DEFINITION. A path µ is non dominated if and only if there is not another path µ ′ ∈ C such as µ ′ ∆ F µ.

In the interval model, it is not possible to associate to each path a finite number of evaluation vectors because the number of scenarios is infinite. However, dominance relation remains defined in this model as follows DEFINITION. A path µ dominates a path µ ′ if and only if c s (µ) ≤ c s (µ ′ ) for all s ∈ S, with at least one strict inequality. The path µ ′ is then dominated by µ that one notes µ∆µ ′ . Whatever the evaluation vector, robust solutions naturally belong to the non-dominated solutions set. Thus, the problem can be first to determine all non-dominated solutions (see for example [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF]). EXAMPLE. For the graph in figure 2, and regarding to the evaluation vector V (µ) (in table 1), all solutions are non-dominated excepted µ 4 which is dominated by µ 2 ; regarding to the desutility vector (in table 3), non-dominated solutions are µ 1 , µ 2 , µ 8 ; and regarding to the Lorenz vector, non-dominated solutions are µ 2 and µ 8 . Let us remark that the path µ 4 which is optimal for the worst case criterion is a dominated path.

The main difficulty comes from the possible huge number of non-dominated paths.

Hansen in [START_REF] Hansen | Bicriterion path problems[END_REF] has defined a bicriteria graph for which the number of non-dominated paths is an exponential function of the graph order. Perny and Spanjaard showed in [START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF] that the non-dominated solutions set according to Lorenz evaluation vectors is a subset of the non-dominated solutions set according to V (µ) vectors. Thus, in the graph proposed by Hansen, only two paths remain non-dominated according to Lorenz evaluation vectors. However, in [START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF], a graph with an exponential number of non-dominated paths according to Lorenz evaluation vectors is proposed.

Consequently, the determination of all non-dominated solutions is not possible in general case. Other procedures must be defined for aggregating evaluation vectors in order to provide one or a small size set of robust solutions. Let us mention an alternative approach based on a lexicographic procedure. This approach is applied in [START_REF] Kalai | Robust 1-median location problem on a tree[END_REF] on the disutility vector for the 1-median location problem.

These three approaches are quiet different. Classical criteria coming from decision theory only take into account extreme scenario. The methodology introduced by Bertsimas and Sim represents a way to qualify worst case analysis by considering that only a subset of coefficients will vary in the bad sense. In the approach coming from the decision theory, a solution is robust when it optimizes a particular criterion. In the approach coming from multicriteria analysis, the concept of robustness is not characterized anymore by optimality on a single criterion, but by a list of principles and conditions that leads to determine a set of robust solutions (this set being able to be empty !).

Complexity and resolution of robust shortest path problems in the interval model 4.1 With the worst case criterion

This version of the robust shortest path problem, noted ROBINTWOR, is studied in [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF]. Let us recall that, in this version, a path µ has a value v WOR (µ) = max s∈S c s (µ) and the problem is to determine the optimal path that minimizes this value on all paths. Given a path µ from 1 to n, the scenario which maximizes c s (µ) is the one for which each arc u ∈ U has the higher possible value, that is to say B u . Since this worst case scenario, noted s B , is unique, it is enough to consider the graph evaluated by this worst case scenario, and to determine the shortest path which exactly corresponds to µ * WOR since v WOR (µ * WOR ) = min µ∈C B(µ). Consequently, THEOREM. [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF] The ROBINTWOR problem is polynomial.

EXAMPLE. In the graph of the figure 1, the optimal path according to the worst case criterion is µ * WOR = (1, 2, 6, 7) = µ 1 of value 19.

With the maximum regret criterion

This version of the robust shortest path problem, denoted ROBINTREG, is studied in [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF][START_REF] Karaşan | The robust shortest path problem with interval data[END_REF][START_REF] Montemanni | An exact algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Montemanni | The robust path problem with interval data via benders decomposition[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Zieliński | The computational complexity of the relative robust shortest path problem with interval data[END_REF]. Most results are based on the following property, established by Karaşan, Pinar and Yaman. Let us first recall that, in this problem version, a path µ has the value v REG (µ) = max s∈S r s (µ) = max s∈S (c s (µ) -c s (µ * G s )).

Propriété 1 [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF] Given a path µ from 1 to n, the scenario, denoted s(µ), which maximizes r s (µ) is the one for which each arc (i, j) belonging to µ has a value equals to its higher possible value, in other words c The scenario s(µ) is called the scenario induced by µ. The problem to determine the robust path, according to the maximum regret criterion, is to find µ * REG such as :

v REG (µ * REG ) = min µ∈C (c s(µ) (µ) -c s(µ) (µ * G s(µ) ))
EXAMPLE. For the graph of the figure 1, the table 4 presents the maximum regret value of each path. The path µ 8 is optimal for the maximum regret criterion (µ 8 is also the optimal path for the best case criterion).

µ c s(µ) (µ) c s(µ) (µ * G s(µ) ) v REG (µ) µ 1 = (1, 2, 6, 7) 19
Unfortunately, the difficulty comes from the fact that the number of elementary paths from 1 to n may be exponential.

Complexity

This problem was shown to be NP-hard for directed graphs by Zieliński in [START_REF] Zieliński | The computational complexity of the relative robust shortest path problem with interval data[END_REF] with a reduction to a particular version of the partition problem known as being NP-hard (see on this subject [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]). In parallel, Averbakh and Lebedev established in [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF] that ROBINTREG is strongly NP-hard for non-directed graphs, by making a reduction to the Hamiltonian path problem, denoted HAMIL. They notice that their result can be easily extended for the case of acyclic directed graphs with a layered structure. In the following, we present this extension. Let us first recall that a graph has a layered structure if it is possible to partition the vertices set X into disjoint subsets X 1 , . . . , X g , called blocks, such as each arc goes from a vertex of a block X j to a vertex of the next block X j+1 .

THEOREM. [START_REF] Averbakh | Interval data minmax regret network optimization problems[END_REF] The problem ROBINTREG is NP-hard even for the acyclic directed graphs with a layered structure.

To prove this theorem, we have to introduce the decision version of the problem RO- BINTREG which is defined by : Instance : an acyclic directed graph G = (X, U ) with a layered structure, having two particular vertices 1 and n, whose arcs u ∈ U are valued by intervals [b u , B u ] and an integer M , Question : does there exist a path from 1 to n in G with a maximum regret value lower or equal to M ?

The HAMIL problem is defined as follows :

Instance : a non-directed connected graph F = (V, E).

Question : does there exist in F an Hamiltonian chain, that is to say a chain containing each vertex only once ?

An instance F = (V, E) of this problem, with |V | = p, can be polynomially reduced to an instance of the decision problem ROBINTREG in the following way. Vertices of G are vertices 1, n and 2p copies of the set V . The copy numbered i, denoted V i , is the block i of G. For any vertex v ∈ V , we note v i its copy in the block i, for i = 1, . . . , 2p. Thus, we have X = (1, V 1 , . . . , V 2p , n), with |X| = 2 + 2p 2 . The set U of G is defined as follows :

-arcs

(1, v), for any vertex v ∈ V 1 , -arcs (v, n), for any vertex v ∈ V 2p , -arcs (v i , v i+1
), for any vertex v ∈ V with i = 1, . . . 2p -1, these arcs will be called horizontal arcs, -arcs (v 2i , w 2i+1 ) and (w 2i , v 2i+1 ), for all i = 1, . . . p -1 and for all arcs (v, w)

belonging to E. The set of horizontal arcs is noted H. Any arc of U which is not horizontal is called diagonal. The set of diagonal arcs is denoted D, among which we distinguish the subset D containing arcs of D not linked to 1 nor n. Intervals associated to horizontal arcs are [0, 1], and those associated to diagonal arcs are [START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF][START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF].

In the figure 3, an example of graph F with 3 vertices is represented on the left and the graph G corresponding to the reduction is given on its right (in which intervals [START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF][START_REF] Aissi | Complexity of the min-max and minmax regret assignment problems[END_REF] are replacing by the value 1). Let us observe that the vertices of the even blocks V 2i , i = 1, . . . , p can be reached by some vertices of the block V 2i-1 only with horizontal arcs. For any vertex v ∈ V , the path For a path µ from 1 to n, we denote |µ| its number of arcs and µ its vertices belonging to V 1 ,..., V 2p . By definition of scenario induced by µ and according to upper bounds on arcs of the graph G, we have : c s(µ) (µ) = |µ| = 2p + 1. Moreover under scenario s(µ), any arc of D and any arc of H which belongs to µ has a unit cost, whereas the cost of any arc of H which does not belong to µ is equal to 0. Consequently, the cost of a path λ from

(1, v 1 , . . . , v 2p , n) is called a v-tunnel. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ >0, 1@ i j k i 1 j 1 k 1 i 3 j 3 k 3 i 2 j 2 k 2
1 to n in s(µ) is : c s(µ) (λ) = |D ∩ λ| + |H ∩ λ ∩ µ| = 2 + | D ∩ λ| + |H ∩ λ ∩ µ|. With f (µ, λ) = c s(µ) (µ) -c s(µ) (λ), we have : f (µ, λ) = 2p -1 -| D ∩ λ| -|H ∩ λ ∩ µ| (1)
Let us suppose that there exists an Hamiltonian chain in F denoted (v 1 , . . . , v p ). Then, the sequence

(1, v 1 1 , v 1 2 , v 2 3 , v 2 4 , . . . , v p 2p-1 , v p 2p , n) is a path µ from 1 to n in G.
Since each tunnel T does not have any arc in D and exactly one horizontal arc in common with µ, we have f (µ, T ) = 2p -2. Moreover, since any path λ from 1 to n which is not a tunnel has at least one arc in D, we have :

f (µ, λ) ≤ 2p -2. Consequently, v REG (µ) = max λ∈C f (µ, λ) = 2p -2
Let us now consider an optimal path µ from 1 to n whose maximum regret is lower or equal to 2p -2. T is a tunnel such that k = |H ∩ T ∩ µ| = |T ∩ µ| is minimum. Since µ is optimal with a value lower or equal to 2p -2, and according to the equation 1, we have : f (µ, T ) = 2p -1 -k ≤ 2p -2. This implies k ≥ 1. Thus each tunnel intersects µ with at least k different horizontal arcs, and one needs at least p -1 diagonal arcs in µ to connect together these k arcs. So, we have :

|µ| = 2p -1 ≥ kp + p -1 implying k ≤ 1.
Consequently, k = 1, f (µ, T ) = 2p -2 and v REG (µ) = 2p -2 with exactly one horizontal arc of the form (v j , v j+1 ) ∀v ∈ V and exactly one diagonal arc of the form (v 2i , w 2i+1 ) ∀I = 1, . . . , p -1 in µ. Finally, we obtain an Hamiltonian chain in F from the diagonal arcs of µ.

Resolution

Several algorithms for exactly solving ROBINTREG have been proposed [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF][START_REF] Montemanni | An exact algorithm for the robust shortest path problem with interval data[END_REF][START_REF] Montemanni | The robust path problem with interval data via benders decomposition[END_REF][START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF]. In these studies, ROBINTREG is written as an integer linear program with variables y ij which represent a path µ as follows :

y ij = 1 if (i, j) ∈ µ 0 otherwise
The integer linear program, denoted P 0 , is :

P 0                    min max s∈S   (i,j)∈U c s ij y ij -x s   s.c. (i,j)∈U y ij - (k,i)∈U y ki =    1 if i = 1 -1 if i = n 0 otherwise ∀i ∈ X y ij ∈ {0, 1} ∀(i, j) ∈ U
where x s is the length of the shortest path from 1 to n in G s .

According to the property 1 and given a path µ represented by y, the scenario which carries out max s∈S (i,j)∈U c s ij y ij -x s is the induced scenario s(µ). Under this scenario, the length of any arc (i, j) can be written in function of y ij as follows : b ij + (B ij -b ij )y ij . Thus, by introducing variables x i which represent the length of the shortest path from 1 to i under scenario s(µ), Karaşan et al. in [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF] propose a new formulation of ROBINTREG, noted P 1 .

P 1                            min (i,j)∈U B ij y ij -x n s.c (i,j)∈U y ij - (k,i)∈U y ki =    1 if i = 1 -1 if i = n 0 otherwise ∀i ∈ X (1)
x j ≤ x i + b ij + (B ij -b ij )y ij ∀(i, j) ∈ U (2) x 1 = 0 (3) y ij ∈ {0, 1} ∀(i, j) ∈ U x i ≥ 0 ∀i ∈ X [4, 6] [4, 7] [2, 3] [2, 5] [1, 2]

With the mathematical programming methodology

In [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF], authors show that the problem P ROB presented in section 3.2 can easily be solved by solving at most m + 1 shortest path problems. In fact, the optimal solution value of P ROB , denoted Z ⋆ is given by :

Z ⋆ = min k=1,...m Z k where Z k = Γ c k + min y∈Y   (i,j)∈U c ij y ij + k h=1 ( c h -c k )y h  
where it is assumed that the indices of the arcs are ordered such that c 1 ≥ c 2 ≥ . . . c m .

Consequently, in this approach, the robust version presents the same complexity as the nominal one. Thus, in the case of the shortest path problem, the robust version can be polynomially solved which makes this approach very attractive. This version of the robust path problem, denoted ROBDISWOR, is studied in [START_REF] Kouvelis | Robust dicrete optimization and its applications[END_REF][START_REF] Yu | On the robust shortest path problem[END_REF]. Yu and Yang show that this problem is weakly NP-difficult if the number of scenarios is bounded by a constant and strongly NP-difficult otherwise. Indeed, they show in [START_REF] Yu | On the robust shortest path problem[END_REF] that the 2-partition problem Instance : a set I of m elements and a size a i ∈ Z + for each i in I.

Question : Does there exist a sub-set I ′ ⊆ I such as i∈I ′ a i = i∈I\I ′ a i ? is reduced to ROBDISWOR problem defined as follows :

Instance : a connected graph G = (X, U ) with 2 scenarios.

Question : Does there exist a path µ from 1 to n such as v WOR (µ) = v ?

For that, we only have to consider the graph G = (X, U ) reduced to the 2-partition problem (represented in the figure 5) without directed cycle valued by two scenarios. This graph presents 2m + 2 levels with X = X 0 ∪ X 1 ∪ . . . ∪ X 2m+1 where X 0 = {1}, X 2m+1 = {n} (with n = 4m + 2) and X i = {x i,1 , x i,2 }. There are three categories of arcs in U defined as follows :

-

U 1 = {(1, x 1,1 ), (1, x 1,2 ), (x 2m,1 , n), (x 2m,2 , n)}, each arc (i, j) in U 1 is valued by {0, 0} -U 2 = m-1 k=1 {(x 2k,i , x 2k+1,j )/i = 1, 2 ; j = 1, 2}, each arc (i, j) in U 2 is also valued by {0, 0} -U 3 = {(x 2k-1,i , x 2k,i )/i = 1, 2 ; k = 1, . . . , m}, each arc in U 3 is valued in a different way : c 1 x 2k-1,i ,x 2k,i = a k if i = 1 0 if i = 2 c 2 x 2k-1,i ,x 2k,i = 0 if i = 1 a k if i = 2 … … {0,0} {0
I ′ = {k/(x 2k-1,1 , x 2k,1 ) ∈ µ ∀k = 1, . . . , m} I \ I ′ = {k/(x 2k-1,2 , x 2k,2 ) ∈ µ ∀k = 1, . . . , m} Thus c 1 (µ) = k∈I ′ a k and c 2 (µ) = k∈I\I ′ a k .
(µ) = max{c 1 (µ), c 2 (µ)} = k∈I a i 2
, this value being the optimal path value µ * PIR .

Resolution

Yu and Yang in [START_REF] Yu | On the robust shortest path problem[END_REF] propose an exact algorithm for solving ROBDISWOR when the number of scenarios is bounded. It is based on the dynamic programming principle with a pseudo-polynomial time complexity. In particular for layered graphs, the complexity is O(|U |(L max ) q ) where L max = max s∈S L s with L s denoted the length of the longest path from 1 to n for the scenario s. Yu and Yang also propose in [START_REF] Yu | On the robust shortest path problem[END_REF] an approximate algorithm, denoted H. For layered graphs, the complexity is O(|U |q). This algorithm consists to compute the shortest path for each scenario and, for a fictitious scenario which is an average of the q scenarios, to determine the path which minimizes the worst case criterion. Given µ h WOR the path determined by H, the authors show that :

v WOR(µ H WOR ) v WOR(µ * WOR )
≤ q max s∈S c s (µ H WOR ) min s∈S c s (µ H WOR ) max s∈S c s (µ H WOR ) min s∈S c s (µ H WOR ) + q -1

With the maximum regret criterion

Yu and Yang in [START_REF] Yu | On the robust shortest path problem[END_REF] show that the 2-partition problem is reduced to ROBDISREG, for which the problem is to decide if there is a path µ from 1 to n such as v REG (µ) = v. The reduction presented in the previous section remains valid since v REG (µ) = v WOR (µ) because c 1 (µ * G 1 ) = c 2 (µ * G 2 ) = 0. In addition, exact and approximate algorithms for solving ROBDISWOR can be applied, after some minor modifications for solving ROBDISREG.

With the multicriteria methodology

In the discrete set of scenarios model, the problem of determining all non-dominated paths can be solved by applying algorithms defined in multicriteria analysis as suggested in [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF]. Two types of algorithms are proposed in the literature for determining all nondominated paths in a multicriteria graph : graph algorithms which generalize classical monocriterion graph algorithms to the multicriteria case and, those based on the enumeration of the k shortest paths. The efficiency of this approach rapidly decreases when the number of scenarios increases since the number of non-dominated paths significantly increases with the number of scenarios.

Concerning the problem to determine all Lorenz non-dominated paths, Perny and Spanjaard propose in [START_REF] Perny | An axiomatic approach to robustness in search problems with multiple scenarios[END_REF] an A * algorithm.

Conclusion

Robust path problem has been extensively studied. For most of the considered models, robust version of the shortest path problem becomes NP-difficult, excepted for the worst case analysis with the interval model which is tractable in polynomial time. However, the worst case analysis supposes that the scenario that will be realized will adversely affect the solution. This hypothesis may not be relevant in some decision context. In such cases, new models of robustness have to be proposed.

Concerning the modeling of uncertain, undetermined and random factors, it can be relevant in some context to consider them on graph structure and not only on arcs' value. In such a model, a scenario may be a particular partial subgraph. Such a "structural" model can be seen as an extension of probabilistic combinatorial optimization (cf [START_REF] Murat | The probabilistic longest path problem[END_REF] for the study of the longest probabilistic path).

  In the interval model, each arc (i, j) is associated to an interval, denoted [b ij , B ij ], such as c ij ∈ [b ij , B ij ]. This interval represents the set of possible values of the arc (i, j). The set S of scenarios is infinite and is defined as the cartesian product of the m intervals [b u , B u ]. In this context, a path µ can take any value belonging to the interval [b(µ), B(µ)] with b(µ) = (i,j)∈µ b ij and B(µ) = (i,j)∈µ B ij .

FIG. 2 -

 2 FIG. 2 -Example of scenarios model

  s∈S r s (µ) EXAMPLE. Let us consider the path µ = (1, 2, 4, 5, 7) of the graph in the figure 1 and the scenario s b in which each arc value of U is set to its lower bound. Then, as the shortest path of G s b is µ * G s b = (1, 3, 5, 7), we have : r s b (µ) = 5 -3 = 2. In fact, we will see in the section 4.2 that the maximum regret associated to µ is of 19, and thus : v REG (µ) = 19.

13 µ 2 =TAB. 2 -

 22 Paths value on classical criteria robustness in term of relative deviation which consists in normalizing the regret measure as follows :

ǫ

  will be empty, and the cardinality of C ROB ǫ increases with ǫ. Otherwise, if ǫ is too large, then C ROB ǫ will contain solutions with bad evaluations on some scenarios. Consequently, it is particularly interesting to determine the smallest value of ǫ such as C ROB ǫ contains at least one solution. Averbakh shows that this value is not other than v REG (µ * REG ). Indeed, solutions of C ROB ǫ are such that :

=

  B ij , and each arc (k, h) not belonging to µ has a value equals to its lower bound, in other words c s(µ) kh = b kh .

TAB. 4 -

 4 Maximum regret value of each path from 1 to 7

FIG. 3 -

 3 FIG. 3 -Example of the reduction of Hamiltonian path problem to ROBINTREG problem

FIG. 4 -

 4 FIG. 4 -Dominance test for graph with intervals

5 Complexity and resolution of robust shortest path pro- blems in the discrete set of scenarios model 5

 5

FIG. 5 -

 5 FIG. 5 -Reduction of the 2-partition problem to the ROBDISWOR problem

  Consequently, a 2-partition exists if and only if there exists a path µ from 1 to n in G such as v PIR

P 1 is thus a mixed linear program. Karaşan et al. in [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF] solve it using a linear programming solver. However, when G is of big size, P 1 cannot be solved exactly. The difficulty comes from the constraints (2) which, if deleated, would reduce P 1 to a simple shortest path problem. Also, in [START_REF] Karaşan | The robust shortest path problem with interval data[END_REF], authors propose to apply a preprocessing procedure which removes some constraints (2), those associated with some arcs that cannot belong to the optimal path. By reducing the size of P 1 , this procedure makes possible to increase the size of exactly solved problems.

More recently, Montemanni et al. proposed two algorithms to solve exactly the problem : a dedicated algorithm presented in [START_REF] Montemanni | An exact algorithm for the robust shortest path problem with interval data[END_REF], and a branch and bound algorithm presented in [START_REF] Montemanni | A branch and bound algorithm for the robust shortest path problem with interval data[END_REF]. In [START_REF] Montemanni | The robust path problem with interval data via benders decomposition[END_REF], authors propose to apply a Benders decomposition scheme on P 1 . A great number of experiments is carried out to compare these various approaches. It seems that the algorithm resulting from the Benders decomposition is most powerful to solve most of the considered problems.

With the multicriteria analysis methodology

In the interval model, a path µ dominates a path µ ′ , denoted by µ∆µ ′ , either if δ * < 0 with δ * = max s∈S c s (µ) -c s (µ ′ ), or [δ * = 0 and ∃s ∈ S : c s (µ) < c s (µ ′ )]. The complexity of this dominance test comes from the infinite set of scenarios to be considered. Dias and Climaco studied this problem in [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF] for a more general model (for which the interval model is a particular case). They introduced binary relations to compare path evaluation vectors on the basis of two extreme scenarios only, the best case and the worst case scenarios (already introduced in section 4.1). In the best case scenario, denoted s b , the value of each arc u ∈ U is equal to the smallest cost, that is to say c s b u = b u . They defined the following binary relations :

On the basis of these three relations, they established the following results in the comparison of two paths µ and µ ′ of C :

µ∆µ ′ ⇒ µ <≈ µ ′ , with the corollary : if µ is not <≈-dominated then µ is not dominated. From these results, they proposed an algorithm, based on the enumeration of k shortest paths, to determine the set of non-dominated paths. In this algorithm, paths are enumerated in ascending order of their value on the scenario s b , then <≈-dominated and ≪dominated paths are removed, and finally, the complete dominance test is carried out only on remaining paths in order to eliminate the dominated ones.

In the specific case of interval model, the complete dominance test has not to be carried out. The property below allows to conclude by considering only the extreme best and worst case scenarios. Let us first denote by µ \ µ ′ the set of arcs that belong to µ and not to µ ′ .

with the dominance property of µ for the specific scenario s(µ), we obtain :

REMARK. If µ and µ ′ have not any joint arc, then the property 2 becomes :

EXAMPLE. In the graph represented in the figure 4, µ = (a, b, d, e) dominates µ ′ = (a, c, d, e). And, it is checked that c

From the property 2, it is possible to propose an algorithm, similar to the one proposed by Dias and Climaco in [START_REF] Dias | Shortest path problems with partial information: models and algorithms for detecting dominance[END_REF], based on the enumeration of the k shortest paths. Ones have to enumerate paths in ascending order of their value on the best case scenario and, in the event of equality, by ascending order of their value on the worst case scenario. Consequently, the ith enumerated path, denoted µ i , cannot be dominated by µ k if i < k. On the other hand, µ i dominates µ k if and only if c s B (µ i \ µ k ) ≤ c s b (µ k \ µ i ). This test is the single test to be carried out for each enumerated path.


The tsunami named CRISPR/Cas9

It is rare to witness a breakthrough technology that results in a multidimensional revolution in human health that also has impacts on animals and plants as well as biodiversity and the environment. The tsunami associated with the latest genomeediting techniques is most likely not comparable to anything we have known thus far. In addition, the technology is not only relatively easy to deploy, but also developing at a dizzying pace.

Targeting the genome to change the sequence of a gene and its pattern of expression is not new. But, without question, the use of CRISPR (clustered regularly interspaced short palindromic repeats)/Cas9 [START_REF] Mojica | On the Origin of CRISPR-Cas Technology: From Prokaryotes to Mammals[END_REF] represents a major technological revolution. Indeed, this is the latest advance of a technology that allows the specific addition, removal or modification of DNA sequences, summarized by the term 'genome editing' [START_REF] Gaj | 3rd, ZFN, TALEN, and CRISPR/Cas-based methods for genome engineering[END_REF]. If the genome-edited sequence corresponds to a gene, then the amino-acid sequence of the protein encoded by the gene may then be altered and, in some cases, lead to changes in its activity and function and/or its location or lifespan. Conversely, genome editing may result in the correction of the defective function of a gene within a specific biological context. CRISPR/Cas9 induces a double-strand break in DNA at selected sites in the genome of any cell of any species. In practice, guide RNA (gRNA) leads the DNA endonuclease Cas9 to a specific sequence with instructions to cut through the DNA strands. The gRNA must be complementary to the chosen target sequence and located next to a short DNA sequence motif called 'PAM' (protospacer adjacent motif) to allow Cas9 to bind to the target genomic locus. The cell may then use two different mechanisms to repair the break: non-homologous end joining (NHEJ); or homology-directed repair (HDR). If the objective is to knock down the targeted gene expression, it is sufficient to allow NHEJ to mend the break. However, as NHEJ is prone to error, the 'repaired gene' will most likely be mutated by the insertion and/or deletion (INDEL) of random nucleotides. If the objective is to correct a preexisting mutation, then the repair has to restore the 'normal' sequence. To do this, HDR requires the introduction of a template DNA sequence, thereby allowing the cell to repair the break by copying the template sequence. This also applies when introducing a mutation to mimic a gene variant.

Given this rather simple scheme, the imagination of researchers seems to be without limits, as many technical adaptations have already been made to, for example, simultaneously modify multiple targets, use a dead Cas9 molecule, drive the increased/decreased expression of a gene, or of a fluorophore [START_REF] Barrangou | Applications of CRISPR technologies in research and beyond[END_REF], or develop a programmable CRISPR system (RCas9) capable of specifically eliminating the toxic RNAs causing dominantly inherited diseases such as myotonic dystrophy type 1 or 2 (DM1/2), Huntington's disease or C9orf72-linked amyotrophic lateral sclerosis (C9-ALS) [START_REF] Batra | Elimination of Toxic Microsatellite Repeat Expansion RNA by RNA-Targeting Cas9[END_REF]. Virtually all branches of the life sciences will soon be penetrated by the rapid development of genome-editing technologies. For humans, genetic changes in somatic cells, germ cells and embryos are clear targets for these new approaches. As for other animals, both livestock and laboratory animals are likely candidates for these new methodological approaches, and the environment and biodiversity will also be clearly among the potentially affected areas. Gene drive approaches where a CRISPR/Cas9 cassette is able to self-perpetuate, thereby rapidly spreading any genetic information among all members of a given population, could be applied for pest control, although this should also raise concerns over its misuse. Of equal concern is that gene-editing technologies could be used for the development of genetic weapons of mass destruction. Several academic institutions and ethics committees, including the US National Academy of Sciences (NAS)/National Academy of Medicine (NAM) 1 and, more recently, the European Academies Science Advisory Council (EASAC) 2 , have addressed the ethical, legal and social aspects (ELSA) raised by these new genomeediting tools. Based on its own report published in December 2015, the INSERM ethics committee organized a meeting in Paris, on 16 March 2016, with a wide range of European stakeholders to reflect upon and foster responsible research using genome-editing technologies [START_REF] Chneiweiss | Fostering responsible research with genome editing technologies: a European perspective[END_REF]. The first ethical concern is to assess the feasibility, efficacy and safety of genomeediting techniques s o t h a t the benefit-to-harm balance of any potential clinical application can be properly evaluated. Because we still lack complete control over CRISPR/Cas9 binding and NHEJ vs HDR intervention after cutting DNA, there is a need to evaluate on-target variants, any potential off-target (cuts at non-selected sites) effects and mosaicisms (partial cuts resulting in different daughter cells, some repaired and some not), as well as epigenetic effects, in both the short and long term. Before such studies are promoted, however, there is a need to define standardized methods. To this end, we called for the establishment of a European Steering Committee (ESC) of experts from a wide range of relevant disciplines as diverse as molecular and cell biology, ecology and a variety of the social sciences [START_REF] Chneiweiss | Fostering responsible research with genome editing technologies: a European perspective[END_REF][START_REF] Hirsch | CRISPR-Cas9: A European position on genome editing[END_REF]. In addition, the ESC should rely on an open and transparent discussion process, including representatives of patient organizations, ethics committees and the economic sector, as well as of the communications sector. A major ethical question is the potential application of genome-editing techniques to humans embryos. France, along with many other member countries, ratified the Oviedo Convention of the Council of Europe, including its Article 13, which is relevant to germline genome editing [START_REF] Hirsch | CRISPR-Cas9: A European position on genome editing[END_REF]. The Article prohibits any genetic modification that might be heritable. However, we believe that now is the time for open discussion of a case-by-case analysis for a limited number of genetic disorders, such as Huntington's disease, which may be prevented by genome editing. Clearly, this is necessary for society to maintain its general confidence in science, and requires the appropriate oversight of any laboratory work or medical application of genomeediting techniques, especially those that are irreversible and permanent. The field of neurology will be impacted by genome-editing techniques in multiple ways. It will allow us to rapidly and easily design cellular and animal models of human neurological and mental disorders with known genetic bases, including most neurodegenerative as well as neurodevelopmental disorders. The new techniques are also changing the game for gene therapy, with ongoing clinical trials of muscular dystrophies, for example. Another ethical challenge is to control the present overhyping of genomeediting techniques. Making certain therapeutic promises may engender dystopian expectations. Thus, it is important to raise awareness of the clear distinction between the care/treatment of human diseases and human enhancement. Finally, attention needs to be drawn to the philosophical concept that opposes the dynamism and plasticity of all living organisms by adhering to the inadequate idea of a human nature founded solely on biological determinism. To do this, we must also foster more debates both within the scientific community and with the rest of civil society.

Hervé

  Chneiweiss, MD PhD Sorbonne Universite, UPMC Univ Paris 06 Institut de Biologie Paris Seine (IBPS) Neuroscience Paris Seine, UMR CNRS 8246, INSERM 1130 F-75005, Paris, France Office tel: 331 4427 5294/Cellular: 336 8221 3045 http://www.ibps.upmc.fr/fr/Recherche/umr-8246

https://www.nap.edu/catalog/24623/human-genome-editing-science-ethics-and-governance

http://www.easac.eu/fileadmin/PDF_s/reports_statements/Genome_Editing/EASAC_Report_31_on_Genome_Editing.pdf