Professor André Rossi

Doctor Sonia Toubaline

PhD supervisors. Safia Fabián Castaño

Laurent Houssin

Dominique Quadri

Maîtresse Ce2a

Belsoeur

Maîtresse Prévost

M Chedid

Mme Foucriat

Mathématiques] • Mme Chemin

Mme Nollent

Éducation Musicale

Alan Mathison

Maurice Diamantini

Chercheur

Julie Sergeant

Daniel Huynh

"Cette thèse en informatique qui a pour sujet, en anglais, "Branch-and- Benders

Technology Introduction

In the context of telecommunications, transportation, and logistics, among others, designing networks based on specific architectures is an important task as it describes how the components and entities should be linked together in order to construct a desired network that performs efficiently and achieves predefined goals.

A typical application of such a network design arises in the field of telecommunication networks, in which user nodes lie on an access network, and are connected to concentrators. These concentrators are linked together to form a backbone network, which is connected to a central unit called the root [START_REF] Gourdin | Telecommunication and location[END_REF]. More applications and references can be found in the survey [START_REF] Klincewicz | Hub location in backbone/tributary network design: a review[END_REF]. There are many ways to design networks and several architectural models can be proposed. In this thesis, we consider a tributary and backbone architecture where we seek to select a set of nodes, called hubs, and interconnect them to define the backbone network. The remaining nodes, called terminals are connected to hubs and form the tributary network. The objective is to determine an efficient and cost-effective tributary and backbone network.

We consider in particular the Ring Star problem where the ring is the backbone network and the star the tributary one. This problem has been studied many times in the literature, and has applications in telecommunications, logistics, urbanism, and more. The famous Traveling Salesman Problem is a particular case of the Ring Star Problem where every node belongs to the ring. Hence, the Ring Star Problem is also NP-Hard. Resilience and survivability are two concepts related to robustness and have been receiving a lot of attention in recent years.

Resilience and survivability are responses to uncertainty that occur when unexpected events disturb the system. There have been applications for resilience and survivability not only in combinatorial optimization but in many fields in sciences, from biology to economy. Thus, we are motivated to introduce during my thesis two variants of the Ring Star Problem, a Survivable one and a Resilient one.

Both variants consider the case where at most one hub fails. In the Survivable variant, the ring star network will be preserved whatever hub fails while in the Resilient variant, two corrective operations occurs when a hub fails to preserve the ring star network.

Chapter 1 contains the state of the art in fields of Networks design, the Ring Star Problem, Robustness, Survivability, Resilience, and presents the Benders Decomposition method used to solve our two variants problems. Chapter 2 introduces the variant "a Survivable variant of the Ring Star Problem named 1-S-RSP".

It studies the case where at most one node in a given subset of so-called uncertain nodes can fail if selected as a hub. The variant's objective is to minimize the ring star network design plus the costs associated with coping with the failure of any uncertain hub. This survivable variant of RSP is modeled as an Integer Linear Program (ILP) and also a Branch-and-Benders-cut decomposition, the subproblem of this decomposition being solved by a polynomial algorithm. Several other improvements are made to both solving approaches, in particular taking advantage of an advanced two-opt heuristic adapted for the survivable case and a transformation of the input instance. Mathematical proofs and extended numerical experiments are carried out.

Chapter 3 is about a second variant of the Ring Star Problem named "Resilient RSP" that is solved using both an ILP and a Branch-and-Benders-cut algorithm.

The Resilient RSP is a problem where when a node fails in a given subset of so-called uncertain nodes two corrective operations occur to repair the Ring Star structure, first, a backup edge is paid to reconnect the ring and all non-hubs that were connected to the failing hub must be reallocated to the nearest remaining hub. Extensive numerical experiments are also carried out. At the end of this chapter, a tradeoff is studied, we address the question of deciding whether the survivable or the resilient approach is the most appropriate one, as a function of the failure duration.

The conclusion in Chapter 4 discusses some limitations of our work and some interesting perspectives. This thesis manuscript ends with a Bibliography section.

Branch-and-Benders-cut exact methods for two fault-tolerant Ring Star problem variants

Chapter 1

State of the Art

This State of the Art is organized in topics, first we review networks design, afterwards the Ring Star Problem which is a network design problem, then we focus on three concepts of uncertainty, robustness, survivability and resilience and finally we cover the Benders decomposition.

Networks design

Networks design is a wide field with many problems that have been studied in the literature. Networks design have applications in telecommunications as it is critical to decide where to locate for instance the antennas or other key structures. In (1993), Kershenbaum [START_REF] Kershenbaum | Telecommunications network design algorithms[END_REF] wrote a book on telecommunications networks design algorithms. Network design also have applications in transportation networks where one should decide where to build stations, roads, bridges, etc. for buses, trucks, airports for planes, ports for boats and so on. Farahani [START_REF] Farahani | A review of urban transportation network design problems[END_REF] et al. (2013) published a review of urban transportation network design problems. It also has applications in supply chain. For instance, in a warehouse implementing a pallet rack storage system, network design may be of great help.

A well known and interesting network design problem is the facility location problem that has been extensively studied in operations research and network design. Shmoys et al. [START_REF] Shmoys | Approximation algorithms for facility location problems[END_REF] (1997) present new approximation algorithms in facility locations problems. In every facility location problem that they study, there is a set of locations where facilities may be built with a fixed cost and a set of clients that are assigned to a facility location with another allocated cost. The objective is to determine a set of locations where facilities are opened and minimize the total facility and assignment costs. In the uncapacitated case, the facility can serve as many clients as necessary and in the capacitated case, each facility can serve at most Q clients where Q is an input parameter. Farahani et al. [START_REF] Farahani | Multiple criteria facility location problems: A survey[END_REF] (2010) present a survey on multiple criteria facility location problems while Ortiz-Astorquiza et al. [START_REF] Ortiz-Astorquiza | Multi-level facility location problems[END_REF] (2018) conduct a review on multi-level facility location problems.

Other famous and attracting problems in networks design are Hub location problems (HLP). HLP are usually harder to solve than facility location problems.

These problems consist of locating hub facilities, designing the network, often deciding the origins and destinations, and choosing the routing of flows through the network, while optimizing an objective function. After a state of the art of hub location problem in Alumur et al. [1] (2008), Alumur et al. [2] (2021) provide insights for better modeling HLPs to help create a roadmap for future HLP research.

Several variants of HLP exist, Martins et al. [START_REF] De Sá | The hub line location problem[END_REF] (2015) introduce the Hub Line Location Problem (HLLP) where the hubs are connected by a line and non-hubs are connected to hubs. They present an exact Benders decomposition algorithm for this problem. A topology that also has a backbone and tributary architecture is the hub-and-spoke system, introduced by O'Kelly [START_REF] O'kelly | A quadratic integer program for the location of interacting hub facilities[END_REF] (1987). Many works on hub-and-spoke problems were published in operations research and location or transportation journals. In a hub-and-spoke structure, every pair of hubs is connected, while non-hubs are connected to the closest hub. Bryan et al. [START_REF] Bryan | Hub-and-spoke networks in air transportation: an analytical review[END_REF] (1999) survey advances in analysis of the hub location problem and its variants including the hub-and-spoke problem.

Another problem that is in the scope of networks design is the Median Cycle Problem (MCP) introduced by Labbé et al. [START_REF] Labbé | Locating median cycles in networks[END_REF] (2005). In this problem, the aim is to determine a single cycle through a subset of nodes involving the sum of the two next costs: a routing cost associated with the aforementioned cycle and the cost of assigning nodes not on the cycle to visited nodes. The objective is to minimize the cycle's cost and the assignment cost subject to an upper bound on the total assignment cost. They present a MILP and enhance it with a class of valid inequalities.

A branch-and-cut algorithm is also described alongside separation procedures.

In the next section, we describe and give a literature review of the Ring Star Problem which is the primary topology of interest in this thesis and is a backbone and tributary structure.

Ring Star Problem

We consider a specific tributary and backbone architecture, a subfield of networks design, called the ring-star network. The problem input is a complete mixed weighted graph, with arcs from and to every node as well as edges between any two different nodes and having a specific node called the depot. The RING STAR PROBLEM (RSP) consists in selecting a subset of hubs including the depot and linking them with edges to form a cycle called the ring. Each remaining node is called a terminal and must be connected to exactly one hub using an arc, which is the star topology part. The objective of RSP is to minimize the sum of three costs corresponding to (i) selecting the hubs, (ii) selecting the edges to form the ring, and (iii) selecting the arcs to connect each terminal to a hub. RSP is known to be NP-hard since the Traveling Salesman Problem is a special case when the assignment costs are large compared to the ring costs. RSP has been widely studied in the literature. Xu et al. [START_REF] Xu | Optimizing a ring-based private line telecommunication network using tabu search[END_REF] (1999) considered a digital data service problem in the telecommunication industry where hubs have to be selected among a given subset and link end offices to hubs at minimum cost.

They model this problem as RSP, propose an Integer Linear Problem (ILP) formulation, and address it with a tabu search method. Labbé et al. [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF] (2004) proposed the first Mixed Integer Programming model, strengthened with valid inequalities resulting of a polyhedral analysis and solved it with a branch-and-cut algorithm.

Kedad-Sidhoum and Nguyen [START_REF] Kedad-Sidhoum | An exact algorithm for solving the ring star problem[END_REF] (2010) later proposed a strengthened approach where the depot is duplicated and that changes the ring to an st-chain that starts from the depot and ends at a special node that is a duplicate of the depot. Their formulation allows to derive facet-defining inequalities and their branch-and-cut algorithm is shown to be more efficient than the cycle based branch-and-cut from Labbé. Simonetti et al. [START_REF] Simonetti | The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm[END_REF] (2011) also proposed a new integer programming formulation. They implemented a branch-and-cut algorithm for RSP based on a reduction of the latter to a minimum Steiner tree problem defined over a layered graph, with the introduction of side constraints.

Several heuristics and approximation algorithms have been proposed to address RSP. Dias et al. [START_REF] Dias | An efficient heuristic for the ring star problem[END_REF] (2006) use a hybrid method composed of a General Variable Neighborhood Search (GVNS) alongside a Greedy Randomized Adaptive Search Procedure (GRASP) to approach heuristically the Ring Star Problem while Calvete et al. [START_REF] Calvete | An efficient evolutionary algorithm for the ring star problem[END_REF] (2013) model the problem using a bi-level optimization formulation and propose an evolutionary algorithm to solve it. Recently, Zang et al. [START_REF] Zang | A hybrid ant colony system algorithm for solving the ring star problem[END_REF] (2020) proposed an ant colony system heuristic for RSP. Chen et al. [START_REF] Chen | Algorithms for the metric ring star problem with fixed edge-cost ratio[END_REF] (2021) gave three approximation algorithms for the RSP with fixed edge-cost ratio. In the variant they studied, the edge and arcs costs are proportional and their ratio is an additional problem input. Baldacci et al. [START_REF] Baldacci | The capacitated m-ring-star problem[END_REF] (2007) studied a variant of the Ring Star Problem, the Capacitated m-Ring-Star Problem which consists of selecting a set of m rings that pass through the depot and non-hubs (customers) and a potential subset of hubs nodes (Steiner nodes), while customers not belonging to any ring must be assigned to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers assigned to the rings is bounded by an input capacity Q. This problem is also a generalization of the Traveling Salesman problem, hence is also NP-Hard. Najiami et al. [START_REF] Naji-Azimi | A heuristic procedure for the Capacitated m-Ring-Star problem[END_REF] (2010) gave a heuristic procedure variant of RSP. They propose two Integer Programming formulations for this problem and strengthen it with valid inequalities. Some hubs may fail, hence building a robust Ring Star network that keeps the structure of the architecture even if one hub fails is an interesting problem to study.

To the best of our knowledge, survivable and resilient variants of RSP have never been studied in the literature. We will consider these two variants in this thesis. Therefore we will review the concepts of robustness, survivability, and resilience in a network design context.

Robustness

Robustness in optimization aims to deal with data uncertainty. When data is uncertain, the question of designing a solution that is relevant towards such uncertainty is natural. Such design is called "Robust". The case study by Ben-Tal and Nemirovski [START_REF] Ben-Tal | Robust solutions of linear programming problems contaminated with uncertain data[END_REF] (2000) on 90 linear programs from the NETLIB collection shows that a solution to a linear program can be completely meaningless with data contaminated with small uncertainty. Two groups of authors independently stud-ied robust optimization, El Ghaoui et al. [18, 19] (1997, 1998) and Ben-Tal and Nemirovski [6, 8, 7] (1998, 1999, 2000). Bertsimas and Sim [START_REF] Berstimas | The price of robustness[END_REF] (2004) introduce a smart way to control what they call "the price of robustness": traditional approaches of robustness are focused on the worst-case scenario, which tends to make robust solutions too conservative (or overly pessimistic). Hence, they propose to use a new input parameter, often denoted by Γ which is an upper bound on the number of parameters that can be simultaneously affected by uncertainty. This gives the decision maker more control over how conservative the robust solution should be. The notion of robustness has many definitions and is frequently revisited and extended, see for instance Kouvelis et al. [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] (1996) and Ben-Tal et al. [START_REF] Ben-Tal | Robust optimization[END_REF] (2009) which are two books with different visions on robust optimization. Kouvelis et al. [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] (1996) deal with decision-making with data uncertainty and a strong importance on operations and production management applications. Roy [START_REF] Roy | Robustness in operational research and decision aiding: A multifaceted issue[END_REF] (2010) studied robustness in operational research and decision aiding and in particular describes "robustness concerns" as an a priori concerns that must be taken into account at the moment the problem is formulated, as opposed to "robustness analysis" or "sensitivity analysis" which are conducted after the problem is solved. More recently, in the context of attack scenarios, robust optimization has also been studied considering multiobjective decision-making. Wang et al. [START_REF] Wang | A computationally efficient evolutionary algorithm for multiobjective network robustness optimization[END_REF] (2021) consider a multiobjective network robustness optimization problem which they solve with a computationally efficient evolutionary algorithm. In all these works described above uncertainty is related to data input. Some other types of uncertainties exist such as those concerned with maintaining network structures after some disturbances when designing it. The conservation of properties when unexpected failures affect the network can be achieved in two different ways.

If the solution can stand the considered class of failures without any corrective action, we talk about survivability, whereas resilience is concerned with the preplanning at the design time of corrective actions, which may incur additional costs when they are applied.

Survivability

In the presence of hazardous events (attacks, failures, and so on), designing a reliable topological network is essential. Survivable network design problems have widely been studied in the literature [27, 33] (1995, 2005). These problems aim at building survivable networks, i.e., networks that remain operational despite the occurrence of failures or attacks. In the field of survivable network design problems, Labbé et al. [START_REF] Labbé | A branch and cut algorithm for hub location problems with single assignment[END_REF] (2005) consider a fully interconnected star problem where the hubs are linked by a clique. The authors perform a polyhedral analysis of the proposed model and solve it with a branch-and-cut algorithm. Fouilhoux et al. [START_REF] Fouilhoux | Survivability in hierarchical telecommunications networks[END_REF] (2012) study a 2-edge connected star problem where the backbone is a 2edge connected subgraph. For all k ∈ N, a graph is k-edge connected, if there are at least k edge-disjoint paths between any two different nodes. In [START_REF] Ekin Karaşan | Survivability in hierarchical telecommunications networks under dual homing[END_REF] (2014), Karaşan et al. consider 2-edge connected star problems where each terminal is connected to two hubs. Both papers provide integer programming formulations and valid inequalities for those problems, analyze facet-defining inequalities and present both heuristic and exact separation algorithms. In such works, the survivability is considered either for both tributary and backbone networks Karsan et al. [START_REF] Ekin Karaşan | Survivability in hierarchical telecommunications networks under dual homing[END_REF] (2014) or only for the backbone network [START_REF] Labbé | A branch and cut algorithm for hub location problems with single assignment[END_REF][START_REF] Fouilhoux | Survivability in hierarchical telecommunications networks[END_REF] (2005, 2012). In both cases, the topological structure may not be preserved if a hub fails. Indeed, as shown in Figure 1.2, the backbone structure is not connected anymore when the shaded hub fails.

Resilience

Resilience is often described in the literature as when a system or a network gets damaged, how long or how much resource or energy will it need to recover its full functionality. Holling [START_REF] Holling | Resilience and stability of ecological systems[END_REF] (1973) first introduced the term of resilience in the context of ecology. Since then, in the field of computer science, Liao et al. [START_REF] Liao | A resilience optimization model for transportation networks under disasters[END_REF] (2018) have proposed a resilience optimization model for transportation networks under natural or man-made disasters. They here describe "resilience" as the faculty to recover from damage under unexpected conditions and seek to improve the resilience of transportation infrastructures.. Zang et al. [START_REF] Zhang | A stochastic programming approach for resilient hub location in power projection network considering random hub failures[END_REF] (2017) study a stochastic programming approach for resilient hub location in a power projection network considering random hub failures. The failures of the hubs, which are critical facilities, due to uncertainty threats like natural disasters or man-made attacks could lead to excessive loss or cost. They have the same definition of resilience as in Liao et al. [START_REF] Liao | A resilience optimization model for transportation networks under disasters[END_REF] (2018), i.e., resilience is the ability of a network to withstand and reduce the impact of damages. In Gu et al. [START_REF] Gu | Performance of transportation network under perturbations: Reliability, vulnerability, and resilience[END_REF] (2020), the performance of a transportation network is studied under three types of perturbations: reliability, vulneralibity and resilience. In An et al. [3] (2015), they study the failures of hubs in a hub-and-spoke network by addressing resilient hub-and-spoke networks where backup hubs and alternative routes are taken into consideration to handle hub failures. They model nonlinear mixed integer formulations for such networks problems.

Benders decomposition method 1.6.1 Litterature review on Benders decomposition method

In this thesis, we resort to the Benders decomposition approach which is implemented in a more efficient way than in the original approach. The combination of Benders decomposition and a cutting plane algorithm is referred to as the Branchand-Benders-cut method Cotado [START_REF] Codato | Combinatorial Benders' cuts for mixed-integer linear programming[END_REF] (2006). The Benders decomposition method has been introduced by Jacques Benders [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF] (1962), it is an exact method and many works have been carried out using this approach since then. It consists of decomposing the studied problem into two problems called master problem and subproblem. The master problem includes the complicating variables and the subproblem is easy to solve once the complicating variables are fixed. At each iteration, the master problem, written as a mixed integer linear program, is solved to optimality, then the subproblem is also solved, using the decision variables of the master problem as input parameters. After solving the subproblem, a feasibility cut or an optimality cut is added to the master problem or the current solution of the master problem is proven optimal. Many papers are related to this decomposition. Geoffrion et al. [START_REF] Geoffrion | Generalized Benders decomposition[END_REF] (1972) generalized Benders' approach to a broader class of programs in which the parametrized subproblem can be non linear and convex instead of being linear. Bloom [START_REF] Bloom | Solving an electricity generating capacity expansion planning problem by generalized Benders' decomposition[END_REF] (1983) used the generalized Benders decomposition from Geoffrion to solve an electricity generating capacity expansion planning problem. In Rahmaniani et al. [START_REF] Rahmaniani | The Benders decomposition algorithm: A literature review[END_REF] (2017) a comprehensive survey of the Benders decomposition algorithm is provided. Dieter et al. [START_REF] Weninger | Benders algorithm with (mixed)-integer subproblems[END_REF] (2019) present two algorithms to clarify some of the Benders decomposition algorithms presented be-tween 2000 and 2010. In general Benders decompositions, we consider problems of the form min{cx

+ dy : Gx + Hy ≥ b, x ∈ N m 1 , y ∈ R m 2 + }.
The problem is split into a master problem on the x variables and a subproblem on the y variables which are generally of linear form. Fakhri et al. [START_REF] Fakhri | Benders decomposition with integer subproblem[END_REF] (2017) consider the case where the subproblem variables are integer and present an exact method for this particular case. Keyvanshokooh et al. [START_REF] Keyvanshokooh | Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decomposition[END_REF]

Illustration of the classical Benders decomposition

We consider the mixed integer linear program below, referred to as the original problem, that will be addressed using the Benders decomposition.

Minimize cx + dy Gx + Hy ≥ b x ∈ N m 1 y ∈ R m 2

+

The input data are as follows: c is a vector of R m 1 , d is a vector of R m 2 , b is a vector of R n , G is an n-by-m 1 real matrix and H is an n-by-m 2 real matrix.

We also make the following two assumptions: first, we suppose there exist n 1 and n 2 such that n 1 ≥ 1 and n = n 1 + n 2 , and H(i, j) = 0 for all (i, j) ∈ {1, . . . , n 1 } × {1, . . . , m 2 }. Hence G, H and the vector b can be partitioned into two blocks having n 1 and n 2 rows:

G = G 1 G 2 m 1 n 1 n 2 H = H 1 H 2 m 2 n 1 n 2 b = b 1 b 2 1 n 1 n 2
Where H 1 is the zero n 1 -by-m 2 matrix. Now, we apply the Benders decomposition of the original problem by creating a master problem and a subproblem, based on a partition of the variables: x are the complicating variables, because once they are fixed, solving for the remaining y variables is an easy problem. In this section, the partition is given, but in general, the user has to determine this partition, that may not be unique.

           Minimize cx + η G 1 x ≥ b 1 x ∈ N m 1 η ≥ 0
The subproblem is denoted by SP( x) because it is solved only once MP has been solved to optimality. The optimal solution of MP is denoted by the pair ( x, η), where x is a constant vector of N m 1 , and η is a constant nonnegative real number. The subproblem is to minimize the contribution of the y-variables in the objective function of the original problem, while satisfying the constraints of the original problem for the (fixed) solution vector x returned by the master problem:

SP( x) :      Minimize dy H 2 y ≥ b 2 -G 2 x y ∈ R m 2 +
It can be observed that SP( x) is a linear program, so it can be solved in polynomial time. We then solve SP( x) to optimality, one of the following four situations occurs.

1. SP( x) turns out to be unbounded. This means that the original problem is also unbounded, and the solution process stops.

2. SP( x) turns out to be infeasible. This means that x, the optimal solution found for the subproblem does not allow to set the y-variables, i.e., ( x, y) is not a feasible solution to the original problem. As a consequence, a Benders feasibility cut must be added to the master problem before iterating the process.

3. SP( x) has an optimal solution y, and η < d y. Then, ( x, y) is a feasible solution to the original problem, but is not optimal, as the contribution of the subproblem in MP (namely η) is not set appropriately. This indicates that a

Benders optimality cut must be added to the master problem before iterating the process.

4. SP( x) has an optimal solution y, and η = d y. Then, ( x, y) is an optimal solution to the original problem, and the solution process stops.

When situations 2 or 3 occur, we need to separate a feasibility cut, or an optimality cut. To do this, we use the fact that SP( x) is a linear program, and consider its dual denoted by DSP( x), whose objective function is to maximize α(b -G 2 x), where α is an n 2 -element vector of decision variables. We now reexamine situations 2 and 3 in more details:

2. SP( x) is infeasible implies that DSP( x) is unbounded. By the Minkowski-Weyl theorem, the feasible set of DSP( x) can be expressed as a convex combination of extreme points, plus a nonnegative linear combination of extreme rays. Since DSP( x) is a maximization problem, there exists an extreme ray in the feasible set representation of DSP( x) that is responsible for its unboundedness. This extreme ray, denoted by α r , should be banned, which leads to an inequality of the form α r (b -G 2 x) ≤ 0. This feasibility cut actually cuts off the current solution x of MP, so it should be added to MP.

3. SP( x) has an optimal solution y that satisfies η < d y. Again, by the Minkowski-Weyl theorem, the optimal solution to SP( x) corresponds to an extreme point α p of the feasible set of DSP( x). Because of this solution, η cannot be less than the optimal objective value of DSP( x), hence α p (b -G 2 x) ≤ η is an optimality cut to be added to MP.

Chapter's abstract

The Ring Star Problem consists in selecting a subset of nodes called hubs including the depot and linking them with a cycle, the remaining nodes being connected to exactly one hub, at minimum cost. We study a survivable variant of the Ring Star Problem where at most one node in a given subset of so-called uncertain nodes can fail if selected as a hub. We model this problem as an Integer Linear Program (ILP), that is also addressed with a Branch-and-Benders-cut decomposition. The Benders subproblem is turned into a linear program with the addition of new inequalities that are shown to be facet-defining, and several enhancements to both the ILP and Branch-and-Benders-cut algorithm are also presented. Both approaches are compared on the basis of extensive numerical experiments that bring the following conclusions. First, the survivable variant is shown to be much harder than the original Ring Star Problem, and the extra cost induced by survivability is significant. Second, the ILP formulation tends to produce tighter lower bounds but memory issues are frequent for large instances. Finally, the Branchand-Benders-cut algorithm returns feasible solutions that are often of better quality than those produced by ILP, and is less frequently subjected to memory issues on the considered set of instances. This chapter's content has been submitted to Networks journal and part of it has been published in INOC [START_REF] Khamphousone | Proc. 10th International Networks Optimization Conference (INOC[END_REF] (2022). It has also been presented in ROADEF 2022.

Chapter's structure

This chapter is structured as follows: in Section 2.3 we introduce the SURVIVABLE RING STAR PROBLEM and present an ILP formulation in Section 2.4. We describe a Branch-and-Benders-cut decomposition in Section 2.5, and propose enhancements in Section 2.6. Finally, numerical experiments are reported in Section 2.7 where both approaches to address the SURVIVABLE RING STAR PROBLEM are compared, and the results are discussed.

Survivable Ring Star Problem definition

We define in Table 2.1 some of the notations used in this work. In this section, we first recall the Ring Star problem and then introduce the Survivable Ring Star Problem.

The input of RSP is the complete mixed graph G = (V, E ∪ A) with |V| = n ∈ N nodes, n ≥ 3 where node 1 is a specific node called the depot, E = {ij| (i, j) ∈ V 2 , i < j} is the edge set and A is the arc set. Building the ring consists of selecting a subset H ⊆ V, which cardinality is not known in advance and 1 ≤ |H| ≤ n, then linking the selected hubs of H by a cycle using |H| edges of E. The depot node has to be in H. The cost of opening a hub i ∈ V is o i ∈ R + and the cost of selecting edge ij ∈ E between hubs i and j is r ij ∈ R + . The star requirement of the problem asks that each terminal in T = V \ H be connected to exactly one hub in H. The cost of selecting arc (i, j) ∈ A to connect terminal i ∈ T to hub j ∈ H is s ij ∈ R + . Finally, the RSP is to design a minimum-cost Ring Star network, where the cost is composed of the sum of selecting the hubs, linking them to form the ring and connecting the terminals.

The SURVIVABLE RING STAR PROBLEM, referred to as 1-S-RSP where 1 is the maximum number of simultaneous hub failures, has one more input than RSP:

V ⊆ V is a subset of nodes that can fail if they are selected as hubs. Following the terminology of Rossi et al. [START_REF] Rossi | Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations[END_REF], the hubs in V are called uncertain, whereas the hubs of V \ V are called certain as they are not supposed to fail. The aim of problem 1-S-RSP is to build a minimum-cost subgraph of G such that if at most one uncertain hub fails, the ring can be restored using a backup edge, and each terminal is still connected to at least one surviving hub. To achieve this, for any uncertain hub, an additional edge has to join its two neighbors in the ring. This edge is called a backup edge, and is used whenever the hub in question fails. Each terminal is connected either to a single certain hub or to two uncertain hubs. Thus, when an uncertain hub fails, the terminals connected to it are still connected to the ring. Note that when V is empty, 1-S-RSP reduces to RSP. Figure 2.1 shows an illustration of a solution to the 1-S-RSP with V = V \ {1, 11}. In this solution, the terminals are T = {2, 3, 7} and the hubs are H = V \ T. Backup edges are shown in blue, and it can be observed that the number of backup edges is equal to the number of uncertain hubs. This property can be shown to hold when the ring is made of 5 or more hubs.

Table 2.1: Table of Notations V Set of nodes, V = {1, 2, . . . , n} V Set of uncertain nodes, V ⊆ V V ̸ = Set of couples of different nodes V ̸ = = {(i, j) ∈ V 2 : i ̸ = j} E Set of edges, E = {ij| (i, j) ∈ V 2 , i < j} A Set of arcs, A = {(i, j)| (i, j) ∈ V ̸ = } J
Set of triplets where the second element is an uncertain node

J = {(i, j, k) ∈ V 3 : j ∈ V, i ̸ = j, j ̸ = k, i < k} s n-

An ILP formulation of 1-S-RSP

In this section, we present an ILP formulation for 1-S-RSP. This ILP exploits the fact that the number of backup edges is equal to the number of uncertain hubs.

However, this property does not hold when the ring contains 3 or 4 hubs, so these two particular cases are dealt with by two brute-force algorithms. Problem 1-S-RSP is then addressed as follows: first, a brute-force algorithm is called for rings containing 3 hubs; second, another brute-force algorithm is used for 4-hub rings;

and third, the ILP formulation where the ring has at least 5 hubs is solved. The best solution found is then returned.

Brute-force algorithms of polynomial time complexity for the cases of three and four hubs

A feasible solution to 1-S-RSP has a three-hub ring only if all these hubs are certain.

Indeed, if one of these three hubs is uncertain, then its failure leaves only two hubs which are not enough to form a ring. The case of a four-hub ring is also special in the sense that a single backup edge can be used to cope with the failure of two different hubs. As shown in Figure 2.2, the backup edge that joins nodes 1 and 3 is used when either hub 2 or 4 fails. It can also be seen that the number of backup edges (two) is not equal to the number of uncertain hubs (three). We introduce two brute-force algorithms to deal with the particular cases where the ring has three or four hubs. Then, the proposed ILP formulation assumes that the ring has at least 5 hubs and the cutoff parameter of the solver is set to the best solution value found by the brute-force algorithms. Hence, the solver stops as soon as it finds out that there is no optimal solution with at least 5 hubs. Algorithms 1 and 2 are based on an exhaustive enumeration to determine an optimal solution with 3 hubs in O(n 3 ) time and 4 hubs in O(n 4 ) time.

An ILP formulation for at least five hubs

The core of the ILP formulation of 1-S-RSP is inspired from [START_REF] Labbé | A branch and cut algorithm for hub location problems with single assignment[END_REF], and uses mostly the same notations. All the decision variables of 1-S-RSP are Boolean, and in the sequel, B denotes the discrete set {0, 1}. The x variables are used to model the selection of the edges of the ring and the y variables model the status of the nodes (to distinguish hubs and terminals), as well as the connection of terminals to hubs. The additional new x ′ variables are introduced to model the selection of the backup edges. More precisely, for all ij in E, x ij is set to one if and only if edge ij belongs to the ring. For the sake of readability, we may sometimes refer to x ij for i > j, in which case x ij is replaced with x ji in the computer implementation. For all (i, j) ∈ V 2 , variable y ij is set to one if and only if terminal i is assigned to hub j ̸ = i. The variable y jj is set to one if j is selected as a hub, and it is set to 0 Algorithm 1: A brute-force algorithm to find a three-hub optimal solution to 1-S-RSP

1 bestobjval ← +∞ 2 bestsol ← ∅ 3 foreach v 1 ∈ V \ ( V ∪ {1}) do 4 foreach v 2 ∈ V \ ( V ∪ {1}) : v 2 > v 1 do 5 currentobjval ← o 1 + o v 1 + o v 2 + r 1v 1 + r 1v 2 + r v 1 v 2 6 foreach v ∈ V \ {1, v 1 ,
(i, k) ∈ V 2 such that i < k, variable x ′
ik indicate whether hubs i and k are the common neighbor of an uncertain hub and thus a backup connection is established between them. Note that the backup edges do not need to form a cycle, as can be seen in the example of Figure 2.1. For the sake of illustration, Figure 2.3 shows all nonzero x, x ′ , and y variables of an 11-node instance of 1-S-RSP, except nonzero y ii variables. The number of edges in the ring is equal to the number of hubs, and there are six backup edges (i.e., nonzero x ′ ij variables) because there are six uncertain hubs. x 4 ,1 1

x 1 , 1 1

x 1 , 5

x 5 , 9

x 6 ,8

x 8 , 1 0 x 9 , 1 0

x ′ 4 , 8
x ′ 6, 10

x ′ 5, 10

x ′ 8,9

x ′ 1, 9

x ′ 6 , 1 1 A brute-force algorithm to find a four-hub optimal solution to 1-S-RSP

1 bestobjval ← +∞ 2 bestsol ← ∅ 3 for v 1 = 2 to n -2 do 4 for v 2 = v 1 + 1 to n -1 do 5 for v 3 = v 2 + 1 to n do 6 currentobjval ← o 1 + o v 1 + o v 2 + o v 3 7 H ← {1, v 1 , v 2 , v 3 } 8 foreach v ∈ V \ {1, v 1 , v 2 , v 3 } do 9 costcertain ← +∞ costuncertain ← [+∞, +∞] foreach h ∈ H do if h ∈ V \ V and s vh < costcertain then costcertain ← s vh else if h ∈ V then if s vh < costuncertain[1] then 16 costuncertain[2] ← costuncertain[1] 17 costuncertain[1] ← s vh else if s vh < costuncertain[2] then 19
costuncertain [2] ← s vh currentobjval ← currentobjval + min(costcertain, costuncertain [1] + costuncertain [2])

/* Testing three solutions based on 1, v 1 , v 2 and v 3 */

sol 1 ← r 1v 1 + r v 1 v 2 + r v 2 v 3 + r 1v 3 if v 1 ∈ V or v 3 ∈ V then sol 1 ← sol 1 + r 1v 2 if 1 ∈ V or v 2 ∈ V then sol 1 ← sol 1 + r v 1 v 3 sol 2 ← r 1v 1 + r v 1 v 3 + r v 2 v 3 + r 1v 2 if v 1 ∈ V or v 2 ∈ V then sol 2 ← sol 2 + r 1v 3 if 1 ∈ V or v 3 ∈ V then sol 2 ← sol 2 + r v 1 v 2 sol 3 ← r 1v 2 + r v 1 v 2 + r v 1 v 3 + r 1v 3 if v 2 ∈ V or v 3 ∈ V then sol 3 ← sol 3 + r 1v 1 if 1 ∈ V or v 1 ∈ V then sol 3 ← sol 3 + r v 2 v 3 if currentobjval + min(sol 1 , sol 2 , sol 3 ) < bestobjval then bestobjval ← currentobjval + min(sol 1 , sol 2 , sol 3 ) bestsol ← {1, v 1 , v 2 , v 3 }
The ILP formulation for 1-S-RSP is as follows:

Min z = ∑ ij∈E r ij (x ij + x ′ ij ) + ∑ i∈V o i y ii + ∑ (i,j)∈A s ij y ij ∑ j∈V i<j x ij + ∑ j∈V i>j x ji = 2y ii ∀i ∈ V (2.1) x(δ(S)) ≥ 2 ∑ j∈S y ij ∀S ⊂ V, 1 / ∈ S, i ∈ S (2.2) ∑ j∈V\ V i̸ =j 2y ij + ∑ j∈ V i̸ =j y ij = 2(1 -y ii ) ∀i ∈ V (2.3) ∑ i∈V ∑ j∈V,i<j
x ij ≥ 5 (2.4)

x ij + x jk ≤ 1 + x ′ ik ∀(i, j, k) ∈ J (2.5)
y ij ≤ y jj ∀(i, j) ∈ A (2.6
)

y 11 = 1 (2.7)
y ij ∈ B ∀(i, j) ∈ V 2 x ij ∈ B ∀ij ∈ E x ′ ij ∈ B ∀ij ∈ E
In the sequel, for any subset S of V, we define δ(S) as the set of all the edges of E that have one endpoint in S and another endpoint in V\S. We also define x(F) = ∑ i∈F,i<j x ij for all F ⊆ E. Constraints (2.1) enforce that each hub is incident to two edges in the ring, and each terminal is incident to zero edges. Constraints (2.2) are connectivity constraints, they are identical to the ones in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF]. They state that any set S that does not contain the depot must be connected to V \ S by at least two edges, if S contains a hub i. In that case, y ii is equal to one, and so is ∑ j∈S y ij . The latter expression appears in the right-and side of (2.2) as the resulting inequalities are stronger when ∑ j∈S y ij is used instead of just y ii . Constraints (2.3) enforce that each terminal is connected to either one certain hub or two distinct uncertain hubs.

Constraint (2.4) states that the ring contains at least five hubs. Constraints (2.5) enforce that edge ik has to be selected as a backup edge if node j is an uncertain hub adjacent to hubs i and k in the ring; there are (2.6) enforce that terminals can be connected to hubs only. Constraint (2.7) sets the depot as a hub, and the remaining constraints define the domain of the variables. This model can be solved using a branch-andcut or a Branch-and-Benders-cut approach where subtour elimination constraints are relaxed and separated on-the-fly when they are found to be violated.

1 2 | V|(n -1)(n -2) = O(| V|n 2 ) such inequalities. Constraints

A Branch-and-Benders-cut decomposition of 1-S-RSP

In the framework of Benders decomposition described in Section 1.6, a new branchand-bound search tree is built from scratch for the master problem, which may not be very efficient. Consequently, we devise a Branch-and-Benders-cut decomposition for 1-S-RSP that differs from the classical Benders decomposition by generating a unique branch-and-bound search tree for the master problem where the subproblem is solved whenever an integer solution is found. The corresponding cuts are added to the master problem following a cutting-plane procedure. This method has been used by Fortz et al. [START_REF] Fortz | An improved Benders decomposition applied to a multi-layer network design problem[END_REF] to address a multi-layer network design problem. Figure 2.4 illustrates with a flowchart the Branch-and-Benders-cut decomposition scheme. In the context of this chapter, the feasibility cuts are subtour elimination constraints and the optimality cuts enforce the contribution of the star cost in the Master problem. Finally, connectivity cuts can also be added to the Master problem at fractional nodes, using the Edmonds-Karp Min cut algorithm [START_REF] Lammich | Formalizing the Edmonds-Karp algorithm[END_REF]. In this section, we propose new subtour elimination constraints for the master problem, and then state the master problem and subproblem of the decomposition. Subsection 2.5.2 shows how to rewrite the latter one as a linear program by adding valid inequalities. In Subsections 2.5.3 and 2.5.4, after decomposing the subproblem into n + 1 smaller linear problems, we give the solution of the dual of each part. Finally, Subsection 2.5.5 presents a polynomial algorithm to solve the subproblem, Subsection 2.5.6 shows the corresponding optimality cuts, and a polyhedral analysis of the valid inequalities added to the subproblem is given in Subsection 2.5.7.

Description of the master problem and the subproblem

If the ring is known, i.e., the y ii variables and the x ij variables are fixed, determining all the remaining variables is easy. Indeed, when the ring has 5 or more hubs,

x ′ ik can be set to one if and only if j ∈ V and

y jj = x ij = x jk = 1. Otherwise, x ′
ik is set to zero. Furthermore, for each terminal i, the optimal decision is to select the option that incurs the minimum cost: the first option consists of connecting terminal i to the closest certain hub, and the second one is to connect it to its two nearest uncertain hubs. As a consequence, we devise a Benders decomposition of the ILP formulation of 1-S-RSP, in which the master problem is to determine the ring, i.e. the y ii and x ij variables, and the subproblem is to complement the ring with backup edges and to connect the terminals to the ring at minimum cost. Before we can apply the Benders decomposition, the subtour elimination constraints (2.2) must be replaced because they mix variables of the master problem (x variables) and variables of the subproblems y ij (when i ̸ = j). We then propose the following constraints to enforce subtour elimination in the master problem:

x(S) ≤ |S| -1 ∀S ⊆ V, 1 / ∈ S (2.8) x(S) ≤ |S| -y ii ∀S ⊆ V, 1 ∈ S, i ∈ V\S (2.9)
In order to show that these inequalities are valid subtour elimination constraints, let RP be the ILP formulation of 1-S-RSP where constraints (2.2) are relaxed. For each feasible solution to RP, let G x = (V, E x ) be the non-directed graph on the vertex set V, where E x = {ij ∈ E : x ij = 1}. This graph represents the edges of the ring and may contain one or more cycles. A cycle in G x that does not contain the depot is called a subtour. A solution to 1-S-RSP is a solution to RP in which the associated graph G x is free of subtours. By constraints (2.1), the vertices in G x have degree 0 or 2, so any feasible solution to RP satisfies the following properties:

Property 1: |S| -x(S) ≥ 0 ∀S ⊆ V.
Proof: We prove this property by contradiction. Assume that there exists S ⊆ V such that |S|x(S) < 0. The quantity x(S) is the number of edges of G x with both endpoints in S, which is also the number of edges of G x [S], the subgraph of G x induced by S. Since each of these edges contributes 2 to the degree sum, we have |S| -

1 2 ∑ i∈S d G x (i) < 0 which is equivalent to: 2|S| < ∑ i∈S d G x (i) Where d G x (i) is the degree of vertex i ∈ V in the graph G x .
After dividing the last inequality by |S|, we obtain that the average degree of the vertices in S is strictly larger than 2 in G x , which is a contradiction as constraints (2.1) enforce that the maximum degree in the ring is 2. ■

Property 2: |S| -x(S) = 0 if and only if G x [S] is a collection of cycles. Proof: We first assume that G x [S] is a collection of cycles. This implies that G x [S] has |S| edges, so |S| = x(S). Conversely, if 2|S| = ∑ i∈S d G x (i), then the average degree is 2 in G x [S], so each node of S must have degree 2, hence G x [S] is a collec- tion of cycles. ■ If G x [S]
is not a collection of cycles, then |S|x(S) ≥ 1 because the left-hand side is an integer quantity. It can be deduced that if G x [S] is a collection of cycles and there exists at least one hub in V\S, then the current solution to RP has a subtour.

So to prevent subtours, one could enforce the following constraints:

|S| -x(S) ≥ 1 |V\S| ∑ i∈V\S y ii ∀S ⊆ V Where 1 |V\S| ∑ i∈V\S y ii is in (0, 1]
if there exists a hub in V\S, and zero otherwise. If S is a subset of V that does not contain the depot, then in that case, |S|x(S) is strictly positive, because 1 ∈ V\S and y 11 = 1. So for all the sets S that do not contain 1, we can strengthen the above inequalities to (2.8). These constraints dominate the above inequalities, since 1

≥ 1 |V\S| ∑ i∈V\S y ii . Now, if S contains 1,
we can also strengthen the inequalities to (2.9). Again, these constraints dominate the above inequalities if we choose i ∈ V\S such that y ii = 1, as we have

y ii ≥ 1 |V\S| ∑ j∈V\S y jj .
The master problem can then be stated as:

Min ∑ ij∈E r ij x ij + ∑ i∈V o i y ii + λ
Subject to (2.1), (2.4), (2.7), (2.8), (2.9) and

y ii ∈ B ∀i ∈ V x ij ∈ B ∀ij ∈ E λ ∈ R +
After solving the master problem, the numerical value of the x ij and y jj variables are stored as xij and ŷjj , then passed to the subproblem, whose primal can be stated as:

Min λ = ∑ ij∈E r ij x ′ ij + ∑ (i,j)∈A s ij y ij ∑ j∈V\ V i̸ =j 2y ij + ∑ j∈ V i̸ =j y ij = 2(1 -ŷii ) ∀i ∈ V (2.10) x ′ ik ≥ xij + xjk -1 ∀(i, j, k) ∈ J (2.11)
y ij ≤ ŷjj ∀(i, j) ∈ A, ( 2.12
) (2.11) and (2.12) are derived from (2.3), (2.5) and (2.6) respectively. This subproblem is easy to solve. Indeed, for each uncertain hub j having hubs i and k as neighbors in the ring, we should set x ′ ik = 1.

y ij ∈ B ∀(i, j) ∈ A (2.13) x ′ ij ∈ B ∀ij ∈ E Constraints (2.10),

Linear programming formulation of the subproblem

If node i is a terminal (i.e., ŷii = 0), we define m i and m ′ i as the two distinct closest hubs in V, and m ⋆ i as the closest hub in V\ V, if they exist. If not, the corresponding values are set to zero.

• m i =      0 if |{j ∈ V : ŷjj = 1}| = 0 arg min j∈ V: ŷjj =1 s ij otherwise • m ′ i =      0 if |{j ∈ V\{m i } : ŷjj = 1}| = 0 arg min j∈ V\{m i }: ŷjj =1 s ij otherwise • m ⋆ i =      0 if |{j ∈ V\ V : ŷjj = 1}| = 0 arg min j∈V\ V: ŷjj =1 s ij otherwise Because m i , m ′ i , and m ⋆ i are indices in V ∪ {0}
, we let 0 be a dummy vertex for which s i,0 is infinite for all i ∈ V. Node 0 cannot be a hub or a terminal and it does not appear in any solution to 1-S-RSP, as its only purpose is to let s i,m i be infinite when there is no uncertain hub, s i,m ′ i be infinite when there is at most one uncertain hub, and s i,m ⋆ i be infinite when there is no certain hub in the ring. If

s i,m i + s i,m ′ i < s i,m ⋆
i , then terminal i is connected to its two closest uncertain neighbors in the ring. Otherwise, terminal i is connected to the closest certain hub in the ring. Since the ring has at most three hubs, s i,m i + s i,m ′ i and s i,m ⋆ i cannot be both set to infinity. If {j ∈ V : ŷjj = 1} is empty, then the linear programming relaxation of the subproblem is integral. Otherwise, the subproblem, originally an integer linear program, can be stated as a linear program by adding the following constraint:

y ik ≤ ∑ j∈ V\{k}: ŷjj =1
y ij for all i ∈ V such that ŷii = 0, and for all k ∈ V such that s ik = min j∈ V: ŷjj =1 s ij . This constraint states that if terminal i is connected to an uncertain hub, then it should be connected to at least another one. If {j ∈ V\{k} : ŷjj = 1} is empty, then this inequality reads y ik ≤ 0 which forbids terminal i to be connected to the unique uncertain hub k.

Since (2.12) dominates (2.13), and because the objective function "pushes" the x ′ variables downward, integrality constraints can be dropped, and it is shown that the linear relaxation of the subproblem (with the new constraints above) has an integral optimal solution.

We can take advantage of the subproblem's structure and decompose it as n + 1 independent subsubproblems: IP 0 sets the backup edges, and for all i ∈ V, IP i sets the y ij variables for all j ∈ V\{i}. The objective function of the subproblem is then the sum of the n + 1 objective values. More precisely, we have:

(IP 0 ) :            Min ∑ ij∈E r ij x ′ ij x ′ ik ≥ xij + xjk -1 ∀(i, j, k) ∈ J x ′ ij ∈ B ∀ij ∈ E (IP i ) :                        Min ∑ j∈V\{i} s ij y ij ∑ j∈V\ V i̸ =j 2y ij + ∑ j∈ V i̸ =j y ij = 2(1 -ŷii ) -y ij ≥ -ŷjj ∀j ∈ V \ {i} y ij ∈ B ∀j ∈ V \ {i} (2.10) (2.12)
First, we show that the LP-relaxation of IP 0 has an integer solution. Indeed, IP 0 is a minimization problem on x ′ variables, they appear in the objective function with a nonnegative coefficient and the constraints allow to set them to their lower bound, which are all integer. Hence, setting x ′ ik to max(0, xij + xjk -1) yields an optimal integer solution. Note that in the LP-relaxation of IP 0 , we can also ignore

x ′ ik ≤ 1,
as there is no optimal solution with x ′ ik > 1. Second, for any given i ∈ V, we search for an optimal solution to IP i . If ŷii = 1, then the unique solution is to set y ij to zero for all j ∈ V \ {i} and it incurs a zero optimal objective value. This solution is also the only one for the LP-relaxation of IP i . Now, let i be a terminal, i.e., ŷii = 0. We distinguish two sub-cases:

• if V is empty, or y ij is set to zero for all j ∈ V \ {i} by constraint (2.12), then constraint (2.10) becomes ∑ j∈V\ V i̸ =j y ij = 1. Then IP i and its LP-relaxation have the same optimal solution, which consists in setting y im ⋆ i to one and all other decision variables to zero, the optimal objective value being s im ⋆ i .

• if V \ ( V ∪ {i}) is empty, or y ij is set to zero for all j ∈ V \ ( V ∪ {i}) by constraint (2.12), then constraint (2.10) becomes ∑ j∈ V\{i} y ij = 2.
Then IP i and its LP-relaxation have an optimal solution in common, that consists in setting y im i and y im ′ i to one and all other decision variables to zero, the optimal objective value being

s im i + s im ′ i .
The remaining cases are less straightforward: node i is a terminal and both the set of uncertain hubs, i.e., ( V \ {i}) ∩ {j ∈ V : ŷjj = 1} and the set of certain hubs, i.e., (V \ ( V ∪ {i}) ∩ {j ∈ V : ŷjj = 1} are nonempty. In that case, the LP-relaxation of IP i may have a non-integer optimal solution. Even if solving IP i remains straightforward, we need to formulate it as a linear program, so that its dual can be solved, as separating Benders optimality cuts requires an optimal solution to the subproblem's dual. To this end, we propose a pure linear programming formulation for IP i , by adding valid inequalities and then showing that the LP-relaxation of this improved formulation is integral. We define

Ω i = {j ∈ V \ {i} : ŷjj = 1, s ij = s im i }
as the set containing all the uncertain hubs that are at minimum distance from terminal i, including hub m i if it exists. We now introduce valid inequalities for IP i to enforce that if a minimum-cost uncertain hub has been selected to connect terminal i, then at least another uncertain hub should be selected as well. This is due to the requirement that any terminal should either be connected to a certain hub, or to two uncertain hubs.

y ik ≤ ∑ j∈ V\{k} ŷjj =1 y ij ∀k ∈ Ω i (2.14)
Let LP + i be the LP-relaxation of IP i with the addition of (2.14). Relaxing the integrality constraints yields to y ij ≤ 1 for all j ∈ V \ {i}, but it can be observed that (2.12) dominate these constraints, so they can be dropped and all decision variables in LP + i are simply subject to non-negativity constraints. We now show that LP + i has an optimal solution that is integral. To this end, we use the following lemma:

Lemma 1. In any optimal solution to LP

+ i , y ij = 0 for all j in V \ ( V ∪ {i}) such that s ij > s im ⋆ i and for all j in V \ {i} such that s ij > s im ′ i .
Proof Lemma 1 is proven by contradiction. Let (y ij ) j∈V\{i} be an optimal solution to LP + i . We first assume that there exists q in V \ ( V ∪ {i}) with s iq > s im ⋆ i and y iq > 0. Then we can transform this optimal solution by increasing y im ⋆ i by y iq and by setting y iq to zero. The resulting solution is still feasible, but since its objective value has decreased by (s iqs im ⋆ i )y iq > 0, the original solution cannot be optimal which is a contradiction.

We now assume that (y ij ) j∈V\{i} is an optimal solution to LP + i such that there exists q in V \ {i} such that s iq > s im ′ i ≥ s m i and y iq > 0. We consider the following two subcases. If s im i = s im ′ i , then both m i and m ′ i are subjected to constraint (2.14). If one of them is not tight, say m ′ i , then we can transform the current optimal solution to LP + i into a feasible solution by increasing y ij and by setting y ij to zero for all j ∈

y im ′ i by ε = min   y iq , 1 2
∑ j∈Ω i \{m ′ i } y ij - 1 2 y im ′ i   > 0
V \ ( V ∪ {i, m ⋆ i }).
This transformation yields a feasible solution and does not change its optimal objective value, since

s ij = s im ⋆ i for all j in V \ ( V ∪ {i}).
Still by Lemma 1, the only values of j ∈ V \ {i} such that y ij can be nonzero in an optimal solution to LP + i are those for which s ij ≤ s im ′ i .

• We first consider the subcase in which s im i = s im ′ i . This implies that constraint (2.14) applies for all j ∈ V \ {i} such that y ij can be nonzero. If constraint (2.14) is tight for both m i and m ′ i , then the corresponding two equalities imply that y im i = y im ′ i are the only nonzero variables for all j in V \ {i}. If constraint (2.14) is not tight for m ′ i , or similarly, for m i , then there exists q ∈ V \ {i, m i , m ′ i } such that y iq > 0 and the current optimal solution to LP + i can be transformed into a feasible solution by increasing y i,m

′ i by ε = min   y iq , 1 2 ∑ j∈ V\{i,m ′ i } y ij - 1 2 y im ′ i 
 > 0 and by decrementing y iq by ε. This transformation yields a feasible solution to LP + i , which is still optimal as the objective value of the initial optimal solution has been added (s im ′ is iq )ε = 0, but the new optimal solution has one nonzero variable less than the original one. This process can be repeated at most | V \ {i, m i , m ′ i }| times to produce a solution in which y im i = y im ′ i are the only nonzero variables for all j in V \ {i}.

s im ⋆ i y im ⋆ i + (s im i + s im ′ i )(1 -y im ⋆ i ) = (s im i + s im ′ i ) + (s im ⋆ i -s im i -s im ′ i )y im ⋆ i subject to 0 ≤ y im ⋆ i ≤ 1. So when s im ⋆ i ≤ s im i + s im ′ i
, the optimal solution is to set y im ⋆ i = 1, which yields an optimal objective value of s im ⋆ i and implies that

y im i = y im ′ i = 0. When s im ⋆ i > s im i + s im ′ i
, the optimal solution is to set y im ⋆ i = 0, which yields an optimal objective value of s im i + s im ′ i and implies that y im i = y im ′ i = 1. This shows that in all cases, an integral optimal solution to LP + i can be found. ■

Computing the dual of LP 0 and LP + i for all the nodes i in V

The dual DLP 0 of LP 0 is

(DLP 0 ) :                Maximize ∑ (i,j,k)∈ J ( xij + xjk -1)β ijk ∑ j∈ V:j̸ =i,j̸ =k β ijk ≤ r ik , ∀ik ∈ E β ijk ≥ 0, ∀(i, j, k) ∈ J (2.15)
For all i ∈ V, the dual of LP + i is denoted by DLP + i and is defined as follows:

If ŷii = 1, (DLP + i ) :                        Max λ i = 2(1 -ŷii )α i -∑ j∈V\{i} ŷjj γ ij 2α i -γ ij ≤ s ij ∀j ∈ V \ ( V ∪ {i}) α i -γ ij ≤ s ij ∀j ∈ V \ {i} α i ∈ R γ ij ≥ 0 ∀j ∈ V \ {i} If ŷii = 0, (DLP + i ) :                                          Maximize λ i = 2(1 -ŷii )α i -∑ j∈V\{i} ŷjj γ ij 2α i -γ ij ≤ s ij ∀j ∈ V \ ( V ∪ {i}) α i -γ ij -δ ij + ∑ k∈Ω i \{j} δ ik ≤ s ij ∀j ∈ Ω i α i -γ ij + ∑ k∈Ω i δ ik ≤ s ij ∀j ∈ V \ (Ω i ∪ {i}) α i ∈ R γ ij ≥ 0 ∀j ∈ V \ {i} δ ij ≥ 0 ∀j ∈ Ω i

Computing optimal primal and dual solutions to the subproblems

For all i ∈ V, we propose a feasible solution to LP + i and a feasible solution to DLP + i and show that they have the same objective value in the primal and in the dual respectively, for providing the proof of their optimality. This common numerical value is the cost incurred by the connection of node i to the ring. The study distinguishes 5 cases.

Case 1: Node i is a hub

For all node i ∈ V such that ŷii = 1, the unique feasible solution to LP + i is to set y ij to zero for all j ∈ V \ {i}, leading to a zero objective value for the primal. Similarly, a feasible solution to DLP + i is to set α i and γ ij to zero for all j ∈ V \ {i}, leading to a zero objective value for the dual. But we can propose an alternative solution, that can be shown to yield stronger optimality cuts. This solution consists in setting

α i = min min j∈V\( V∪{i}) 1 2 s ij , min j∈ V\{i}
s ij , with γ ij = 0 for all j ∈ V \ {i}. This solution is also feasible for DLP + i and leads to a zero objective value as well. Now we show that it produces a stronger optimality cut than the one we get by setting all the dual variables to zero. The optimality cut that we have when dual variables are set to zero for all hubs is

λ ≥ ∑ i∈V, ŷii =0 2(1 -y ii )α i + ∑ (i,j,k)∈ J (x ij + x jk -1)β ijk -∑ (i,j)∈V ̸ = y jj γ ij Now, if we set α i = min min j∈V\( V∪{i}) 1 2 s ij , min j∈ V\{i}
s ij for all i ∈ V such that ŷii = 1, we have the following optimality cut:

λ ≥ ∑ i∈V, ŷii =1 (1 -y ii )α i + ∑ i∈V, ŷii =0 2(1 -y ii )α i + ∑ (i,j,k)∈ J (x ij + x jk -1)β ijk -∑ (i,j)∈V ̸ = y jj γ ij Since ∑ i∈V, ŷii =1
(1y ii )α i ≥ 0, the new optimality cut dominates the original one.

Case 2: Node i is a terminal and s im ⋆ i ≤ 2s im i For all node i ∈ V such that ŷii = 0 and s im ⋆ i ≤ 2s im i , the primal optimal solution consists in connecting i to the certain hub m ⋆ i at a cost of s im i ⋆ , so y im ⋆ i = 1 and

y ij = 0 for all j ∈ V \ {i, m ⋆ i }. A feasible solution to DLP + i can be to set α i = 1 2 s im ⋆ i , γ ij = max(0, s im ⋆ i -s ij ) for all j ∈ V \ ( V ∪ {i}), γ ij = max 0, 1 2
s im ⋆ is ij for all j ∈ V \ {i} and δ ij = 0 for all j ∈ Ω i . Since s im ⋆ i ≤ 2s im i , γ ij = 0 for all j ∈ V such that ŷjj = 1, so the corresponding objective value of the dual is s im ⋆ i .

Case 3: Node i is a terminal and

2s im i < s im ⋆ i ≤ s im i + s im ′ i First, it should be observed that if |Ω i | ≥ 2, then s im i = s im ′ i ,
which contradicts the hypothesis of the present case. Hence we now assume that

|Ω i | = 1.
For all node i ∈ V such that ŷii = 0 and 2s

im i < s im ⋆ i ≤ s im i + s im ′ i , the primal optimal solution consists in connecting i to the certain hub m ⋆ i , at a cost of s im i ⋆ , so y im ⋆ i = 1 and y ij = 0 for all j ∈ V \ {i, m ⋆ i }. A feasible solution to DLP + i can be to set α i = 1 2 s im ⋆ i , γ ij = max(0, s im ⋆ i -s ij ) for all j ∈ V \ ( V ∪ {i}). Now, we consider j ∈ V \ {i}. Since |Ω i | = 1, we have s im i < s im ′ i and the second constraint of DLP + i reads α i -γ im i -δ im i ≤ s im i .
Since ŷm i m i = 1 by definition, we shall have γ im i = 0 to let the objective function be s im ⋆ i . Hence, the only option left to satisfy the constraint is to set

δ im i = 1 2 s im ⋆ i -s im i , which is strictly positive. Now, the third constraint of DLP + i reads: α i -γ ij + δ im i ≤ s ij for all j ∈ V \ {i, m i }.
Replacing α i and δ im i by their values yields:

s im ⋆ i -s im i -γ ij ≤ s ij for all j ∈ V \ {i, m i }. We know that s ij ≥ s im ′ i for all j ∈ V \ {i, m i } such that ŷjj = 1, so setting γ ij = max(0, s im ⋆ i -s im i -s ij ) for all j ∈ V \ {i, m i } ensures that the dual solution is feasible since we can show that γ ij = 0 for all j ∈ V \ {i, m i } such that ŷjj = 1. Case 4: Node i is a terminal and 2s im ′ i ≤ s im ⋆ i
For all node i ∈ V such that ŷii = 0 and 2s im ′ i ≤ s im ⋆ i , an optimal solution to LP + i consists in connecting i to the uncertain hubs m i and m ′ i , at a cost of

s im i + s im ′ i , so y im i = y im ′ i = 1 and y ij = 0 for all j ∈ V \ {i, m i , m ′ i}. A feasible solution to DLP + i can be to set α i = 1 2 s im i + s im ′ i , γ ij = max(0, s im i + s im ′ i -s ij ) for all j ∈ V \ ( V ∪ {i}), γ ij = 0 and δ ij = max 0, 1 2 (s im i + s im ′ i ) -s ij for all j ∈ Ω i and γ ij = max 0, 1 2 (s im i + s im ′ i -s ij ) for all j ∈ V \ (Ω i ∪ {i}). Since s im ⋆ i ≥ 2s im ′ i ≥ s im i + s im ′ i , γ ij = 0 for all j ∈ V such that ŷjj = 1, so the corresponding objective value of the dual is s im i + s im ′ i .
Case 5: Node i is a terminal and

s im i + s im ′ i < s im ⋆ i < 2s im ′ i First, it should be observed that if |Ω i | ≥ 2, then s im i = s im ′ i ,
which contradicts the hypothesis of the present case. Hence we now assume that

|Ω i | = 1.
For all node i ∈ V such that ŷii = 0 and

s im i + s im ′ i < s im ⋆ i < 2s im ′ i ,
s im i + s im ′ i and γ ij = max(0, s im i + s im ′ i - s ij ) for all j ∈ V \ ( V ∪ {i}). We can easily check that for all j ∈ V \ ( V ∪ {i}) such that ŷjj = 1, γ ij is zero. Now, we consider j ∈ V \ {i}. Since |Ω i | = 1, we have s im i < s im ′ i and the second constraint of DLP + i reads α i -γ im i -δ im i ≤ s im i .
Since ŷm i m i = 1 by definition, we shall have γ im i = 0 to let the objective function be s im i + s im ′ i . Hence, the only option left to satisfy the constraint is to set

δ im i = 1 2 s im ′ i -s im i , which is strictly positive. Now, the third constraint of DLP + i reads: α i -γ ij + δ im i ≤ s ij for all j ∈ V \ {i, m i }.
Replacing α i and δ im i by their values yields:

s im ′ i -γ ij ≤ s ij for all j ∈ V \ {i, m i }. We know that s ij ≥ s im ′ i for all j ∈ V \ {i, m i } such that ŷjj = 1, so setting γ ij = max(0, s im ′ i -s ij ) for all j ∈ V \ {i, m i } ensures that the dual solution is has an objective of s im i + s im ′ i , since we can show that γ ij = 0 for all j ∈ V \ {i, m i } such that ŷjj = 1.

Polynomial-time algorithm to the subproblem's dual

Even if the subproblem can be stated as a linear program, it has a cubic number of β ijk variables, which makes it long to solve. In order to solve it faster, we take advantage of the fact that these variables are independent of the other variables. Algorithm 3 solves the dual of Benders subproblem's relaxation. It takes advantage of the fact that at most | V| of the β ijk are non-zeros and compute them in a quadratic running time. Knowing xij and ŷjj , we initially let β ′ j be the adjacency list of node j ∈ V such that ŷjj = 1: β ′ j [1] and β ′ j [2] are its two neighbors in the ring. Note that for all (i, j, k) ∈ J, β ijk ̸ = 0 implies that β ′ j is nonempty (the converse does not hold when some ring costs are zero). Algorithm 3 returns an optimal solution to the subproblem's dual in O(|V| 2 ) time.

Optimality cuts of the Benders decomposition

The optimality cut that is added to the master problem of the Benders decomposition is:

λ ≥ ∑ i∈V 2(1 -y ii )α i + ∑ (i,j,k)∈ J (x ij + x jk -1)β ijk -∑ (i,j)∈A y jj γ ij
When Algorithm 3 terminates, β ijk is set to r ik for all (i, j, k) ∈ J and the optimality cut can be written as:

λ ≥ ∑ i∈V: ŷii =0 2(1 -y ii )α i - ∑ (i,j)∈A: ŷii =0 γ ij y jj + ∑ j∈ V:β ′ j ̸ =∅ (x β ′ j [1]j + x jβ ′ j [2] -1)r β ′ j [1]β ′ j [2]

Polyhedral analysis of constraints (2.14)

In this section, we consider a terminal i ∈ V and show that constraint (2.14) is facet-defining for IP i when H ∩ (V \ V) is nonempty and H ∩ V has cardinality at least three where H = {j ∈ V : ŷjj = 1} is the set of hubs as per the solution of the master problem.

Constraint (2.10) is an equality, so it can be removed by substituting one variable of IP i , say y im ⋆ i . Hence

y im ⋆ i = 1 - ∑ j∈H∩(V\ V) j̸ =m ⋆ i y ij - 1 2 ∑ j∈H∩ V y ij
As a result, the original nonnegativity constraint y im ⋆ i ≥ 0 becomes:

∑ j∈H∩(V\ V) j̸ =m ⋆ i y ij + 1 2 ∑ j∈H∩ V y ij ≤ 1
We can also remove all the decision variables y ij ≤ ŷjj for which ŷjj = 0. This leads to a |H| -1 decision variable formulation of IP i : Algorithm 3: Solving the subproblem's dual of 1-S-RSP

1 Input: ( ŷii ) i∈V , ( xij ) ij∈E booleans 2 Output: (α i ) i∈V , (β ′ j ) j∈ V , (γ ij ) (i,j)∈A , (δ ij ) i∈V: ŷii =0,j∈Ω i 3 foreach j ∈ V do 4 β ′ j ← [ ] 5 foreach i ∈ V do 6 α i ← 0 7 foreach j ∈ V : j ̸ = i do 8 if j > i and xij = 1 and i ∈ V then 9 Append j to β ′ i if j > i and xij = 1 and j ∈ V then Append i to β ′ j γ ij ← 0 foreach i ∈ V : ŷii = 0 do Ω i ← {j ∈ V \ {i} : ŷjj = 1, s ij = s im i } foreach j ∈ Ω i do δ ij ← 0 if s im ⋆ i ≤ 2s im i then α i ← 1 2 s im ⋆ i foreach j ∈ V \ ( V ∪ {i}) do γ ij ← max(0, s im ⋆ i -s ij ) foreach j ∈ V \ {i} do γ ij ← max 0, 1 2 s im ⋆ i -s ij else if 2s im i < s im ⋆ i and s im ⋆ i ≤ s im i + s im ′ i then α i ← 1 2 s im ⋆ i , δ im i ← 1 2 s im ⋆ i -s im i foreach j ∈ V \ ( V ∪ {i}) do γ ij ← max(0, s im ⋆ i -s ij ) foreach j ∈ V \ (Ω i ∪ {i}) do γ ij ← max(0, s im ⋆ i -s im i -s ij ) else if 2s im ′ i ≤ s im ⋆ i then α i ← 1 2 (s im i + s im ′ i ) foreach j ∈ V \ ( V ∪ {i}) do γ ij ← max(0, s im i + s im ′ i -s ij ) foreach j ∈ Ω i do γ ij ← 0, δ ij ← max 0, 1 2 (s im i + s im ′ i ) -s ij foreach j ∈ V \ (Ω i ∪ {i}) do γ ij ← max 0, 1 2 (s im i + s im ′ i ) -s ij else if s im i + s im ′ i < s im ⋆ i and s im ⋆ i < 2s im ′ i then α i ← 1 2 (s im i + s im ′ i ), δ im i ← 1 2 (s im ′ i -s im i ) foreach j ∈ V \ ( V ∪ {i}) do γ ij ← max(0, s im i + s im ′ i -s ij ) foreach j ∈ V \ (Ω i ∪ {i}) do γ ij ← max(0, s im ′ i -s ij ) return (α i ) i∈V , (β ′ j ) j∈ V , (γ ij ) (i,j)∈A , (δ ij ) i∈V: ŷii =0,j∈Ω i (IP i ) :                                      Min s im ⋆ i + ∑ j∈(H\{m ⋆ i })∩(V\ V) (s ij -s im ⋆ i )y ij + ∑ j∈H∩ V (s ij - 1 2 s im ⋆ i )y ij y ij ≤ 1 ∀j ∈ H \ {m ⋆ i } ∑ j∈H∩(V\ V) j̸ =m ⋆ i y ij + 1 2 ∑ j∈H∩ V y ij ≤ 1 y ik ≤ ∑ j∈(H∩ V)\{k} y ij ∀k ∈ Ω i y ij ∈ B ∀j ∈ H \ {m ⋆ i }
Determining the dimension of conv(IP i )

We show that conv(IP i ) has dimension |H| -1. To do so, we build |H| affinely independent points of B |H|-1 in conv(IP i ) as follows:

• Point P m ⋆ i has all its entries equal to zero.

• For all j ∈ (H \ {m ⋆ i }) ∩ (V \ V), point P j is defined by P j j = 1, other entries are zero.

• For all j ∈ H ∩ ( V \ {m i }), point P j is defined by P j j = 1 and P j m i = 1. Other entries are zero, so P j has two nonzero entries.

• Point P m i is defined by P m i j 1 = P m i j 2 = 1 for some j 1 ̸ = j 2 in H ∩ ( V \ {m i }), other entries are zero. Note that j 1 and j 2 can always be found since H ∩ V has cardinality at least three.

We form M, the (|H| -1)-by-|H| matrix using P j as its columns for all j ∈ H. Assuming that the nodes in the set H ∩ (V \ V) are reindexed in {1, . . . , h 1 } (where m ⋆ i has index 1) and the nodes in H ∩ V are reindexed in {h 1 + 1, . . . , |H|}, (where m i has index |H|), we can represent M as:

M =              0 1 • • • 0 0 • • • 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 • • • 1 0 • • • 0 0 . . . 0 • • • 0 1 • • • 0 0 . . . . . . . . . . . . 0 . . . 1 1 0 0 • • • 0 1 • • • 1 0              M ′ =             1 • • • 0 0 • • • 0 0 . . . . . . . . . . . . . . . . . . 0 • • • 1 0 • • • 0 0 0 • • • 0 1 • • • 0 0 . . . . . . . . . 0 . . . 1 1 0 • • • 0 1 • • • 1 0            
To show that the |H| points that constitute the columns of M are affinely independent, we subtract the first column of M to all the other ones in order to create |H| -1 directions, then the first column is removed. This yields M ′ , a block diagonal (|H| -1)-by-(|H| -1) matrix that can be written as diag(A, B). The first diagonal block, denoted by A, is the identity matrix of order andB, which is a square matrix of order |H ∩ V|, can itself be split into diagonal blocks. Block B 1,1 is the identity matrix of order |(H \ {m i }) ∩ V|, block B 1,2 is an |(H \ {m i }) ∩ V|-element column vector full of zeros, except for rows j 1 and j 2 where it has one entries, j 1 and j 2 are two distinct elements of (H

h 1 = |(H \ {m ⋆ i }) ∩ (V \ V)|
\ {m i }) ∩ V. Block B 2,1 is an |(H \ {m i }) ∩ V|-
∑ j∈(H\{m i })∩ V µ j B j = B m i
where B j denotes the j-th column of B and µ j is a real number. This would imply µ j = 0 for all j ∈ (H \ {m i , j 1 , j 2 }) ∩ V, µ j 1 = µ j 2 = 1 and µ j 1 + µ j 2 = 0 because of the last row of B. This system has no solution, which implies that all the columns of B are linearly independent. As a result, det(B) is nonzero and M ′ is non-singular. Consequently, conv(IP i ) has dimension |H| -1.

Showing that constraint (2.14) is facet-defining

We show that for all k ∈ Ω i , the inequality induced by constraint (2.14) is facetdefining:

y ik ≤ ∑ j∈(H∩ V)\{k} y ij
To this end, we find |H| -1 points in conv(IP i ) as we did for showing that conv(IP i ) has dimension |H| -1, but we use k instead of m i and we do not take point P k as it does not satisfy constraint (2.14) to equality. It can be checked that constraint (2.14) is satisfied to equality for all the points P j with j ∈ H ∩ (V \ V) as 0 = 0 and for all P j with j ∈ H ∩ ( V \ {m i }) we have 1 = 1.

We form M k , the (|H| -1)-by-(|H| -1) matrix using P j as its columns for all j ∈ H \ {k}. Assuming that the nodes in the set H ∩ (V \ V) are reindexed in {1, . . . , h 1 } (where m ⋆ i has index 1) and the nodes in H ∩ V are reindexed in {h 1 + 1, . . . , |H|}, (where k has index |H|). Then, we form M ′ k by subtracting the first column to all the other columns of M k and we remove the first column and the last row. This yields the identity matrix of order |H| -2, hence we have found |H| -1 affinely independent points of conv(IP i ) that satisfy (2.14) to equality. This proves that (2.14) is facet-defining.

M k =              0 1 • • • 0 0 • • • 0 . . . . . . . . . . . . . . . . . . . . . 0 • • • 1 0 • • • 0 . . . 0 • • • 0 1 • • • 0 . . . . . . . . . . . . 0 . . . 1 0 0 • • • 0 1 • • • 1              M ′ k =             1 • • • 0 0 • • • 0 . . . . . . . . . . . . . . . 0 • • • 1 0 • • • 0 0 • • • 0 1 • • • 0 . . . . . . . . . . . . . . . . . . 0 • • • 0 0 • • • 1            

An instance transformation for 1-S-RSP

In this section, we propose an instance transformation to modify the expression of the objective function of 1-S-RSP so that the Benders decomposition algorithm performs better. Indeed, when star costs are high, they are "invisible" to the master problem and many optimality cuts are required for improving the lower bound of the master problem which discovers these costs gradually through the introduction of optimality cuts. The proposed transformation aims at transferring as much cost as possible from the subproblem to the master problem in order to improve the lower bound of the latter. The idea is then to minimize the contribution of the subproblem to the original objective function value.

Transformation for the star costs

For all i ∈ V, let c i be the contribution of this node to the solution cost. It is defined as:

c i = o i y ii + ∑ j∈V\( V∪{i}) s ij y ij + ∑ j∈ V\{i} s ij y ij
We can observe that exactly one of the following three situations happens in any optimal solution to 1-S-RSP:

1. Node i is selected as a hub, so y ii = 1 and y ij = 0 for all j ∈ V \ {i}, which yields

c i = o i 2.
Node i is a terminal connected to a certain hub j, so y ij = 1 and y ik = 0 for all k ∈ V \ {j}, which yields c i = s ij 3. Node i is a terminal connected to two distinct uncertain hubs j and j ′ , so

y ij = y ij ′ = 1 and y ik = 0 for all k ∈ V \ {j, j ′ }, which yields c i = s ij + s ij ′
For all i ∈ V, let offset i be a lower bound on the cost incurred by node i if it is a terminal:

offset i = min min k∈V\( V∪{i}) s ik , 2 min k∈ V\{i} s ik
This lower bound returns the minimum over two quantities. The first one is the minimum cost for connecting i to a certain hub, and the second one is the minimum cost for connecting i to two uncertain hubs. We can now express c i as follows:

c i = offset i + o i -offset i y ii + ∑ j∈V\( V∪{i}) s ij -offset i y ij + ∑ j∈ V\{i} s ij - 1 2 offset i y ij
The numerical value of c i can be checked to be correct in the above-mentioned three cases, and it can be observed that the y ij variables are all multiplied by a nonnegative constant. The objective function of the ILP formulation of 1-S-RSP can be updated accordingly.

Transformation of the contribution of backup edges

The presence of backup edges in any optimal solution to 1-S-RSP is the consequence of the selection of hubs in V. So if edge ij is selected as a ring edge (i.e.,

x ij = 1), with i ∈ V, then the selection of this edge implies that a backup edge, incident to j should be present to cope the failure of node i. The cost of this edge is at least min k∈V\{j} r ′ kj and since this backup edge is also connected to another hub, we can raise the cost of edge (i, j) to r ij + 1 2 ϵ j where we define ϵ j = min k∈V\{j} r ′ kj for all j ∈ V, as the minimum cost of a backup edge incident to j. Consequently, the cost of any backup edge (i, j) must be decreased by 1 2 (ϵ i + ϵ j ), which maintains nonnegativity.

                                       offset ← ∑ i∈V offset i o i ← o i -offset i ∀i ∈ V r ij ← r ij ∀i ∈ V \ V, ∀j ∈ V \ V : i < j r ij ← r ij + 1 2 ϵ j ∀i ∈ V, ∀j ∈ V \ V : i < j r ij ← r ij + 1 2 ϵ i ∀i ∈ V \ V, ∀j ∈ V : i < j r ij ← r ij + 1 2 ϵ i + 1 2 ϵ j ∀i ∈ V, ∀j ∈ V : i < j r ′ ij ← r ′ ij -1 2 ϵ i -1 2 ϵ j ∀i ∈ V, ∀j ∈ V : i < j s ij ← s ij -offset i ∀i ∈ V, ∀j ∈ V \ ( V ∪ {i}) s ij ← s ij -1 2 offset i ∀i ∈ V, ∀j ∈ V \ {i}
Consequently the objective function of 1-S-RSP is now:

Minimize offset + ∑ i∈V\ V o i y ii + ∑ i∈V ∑ j∈V i<j r ij x ij + r ′ ij x ′ ij + ∑ i∈V ∑ j∈V\{i} s ij y ij
The advantage of this instance transformation is that the objective value of the master problem gets larger, while the objective value of the subproblem gets smaller (the sum remains the same). The transformation also guarantees that ring costs and star costs remain nonnegative, which is necessary for solving the subproblem, as stated in Subsection 2.5.2. By contrast, transformed hub selection costs o i are unrestricted in sign.

Enhancing and solving the ILP and the Branch-and-Benders-

cut of 1-S-RSP

Introduction of 2-opt backup

In order to improve a 1-S-RSP feasible solution, we introduce a strategy, called x ′ i-1,i+1 is shown and replaced by x ′ i-1,j , and a part of the ring is replaced from

[i -1, i, i + 1, i + 2, . . . , j -1, j, j + 1, j + 2] to [i -1, i, j, j -1, . . . , i + 2, i + 1, j + 1, j + 2]
exactly as in Algorithm 4.

j + 2 j + 1 j j -1 i + 2 i + 1 i i -1
ring edges removed by 2-opt backup unchanged ring edges backup edges removed by 2-opt backup

j + 2 j + 1 j j -1 i + 2 i + 1 i i -

Description of the ILP and Branch-and-Benders-cut algorithms

The ILP model is solved without constraints (2.2). Subtour elimination constraints are separated at fractional nodes using the Edmonds-Karp Min cut algorithm [START_REF] Lammich | Formalizing the Edmonds-Karp algorithm[END_REF] and are added to the model thanks to user cuts callbacks. We stop separating such constraints as soon as 2000 inequalities have been generated. This limitation does not apply to the inequalities that are generated at integer nodes of the solver's branch-and-bound tree under the form of lazy constraints, like the subtour elimination constraints found at integer nodes, and the Benders optimality cuts. Every time an integer solution is found, we check whether it contains a subtour or not.

If it contains a subtour, we add the corresponding violated constraint (2.2), otherwise we try to improve the ring with 2-opt backup from Section 2.6.1. If the improved solution is better than the incumbent, then the incumbent is updated accordingly.

The Branch-and-Benders-cut algorithm is implemented as follows. The instance transformation introduced in Subsection 2.5.8 is first applied. Similarly to ILP, constraints (2.8) and (2.9) are not initially present in the model, and we separate them at fractional nodes of the search tree as in the ILP, using the same limit of 2000 user cuts callbacks. Every time the Branch-and-Benders-cut algorithm finds an integer solution, we check whether it contains a subtour or not. We add a subtour elimination constraint implemented as a lazy constraint if it does have a subtour, otherwise, we call 2-opt backup. If the improved solution outperforms the integer solution of the current node in the search tree, then it replaces it. We then solve the subproblem and submit an optimality cut as in Subsection 2.5.6.

Numerical Experiments

The ILP introduced in Section 2.4 and the Branch-and-Benders-cut algorithm presented in Section 2.5, are implemented with the improvements described in Section 2.6.2, and tested on two classes of instances. Class I is a collection of 32 × 3 = 96 TSP instances taken from TSPLIB [START_REF]TSPLIB 95[END_REF] involving between 51 and 200 nodes. In these instances, the nodes are described by their coordinates. Let l ij be the Euclidean distance between nodes i and j of V. Following [START_REF] Labbé | A branch and cut algorithm for hub location problems with single assignment[END_REF], we define the ring cost by r ij = ⌈αl ij ⌉ and the star cost by s ij = ⌈(10 -α)l ij ⌉ where α is in the set {3, 5, 7}, for all (i, j) in V 2 . The influence of parameter α on solutions structure is shown on Figure 2.6 which originates from Calvete [START_REF] Calvete | An efficient evolutionary algorithm for the ring star problem[END_REF] et al. (2013). Opening costs are zero for these instances, that have been used in [START_REF] Kedad-Sidhoum | An exact algorithm for solving the ring star problem[END_REF] and in [START_REF] Labbé | A branch and cut algorithm for hub location problems with single assignment[END_REF] to compare solution approaches for RSP. Algorithm 4: A 2-opt backup algorithm to improve a feasible solution of 1-S-RSP

1 Input: (x ij ) ij∈E , (x ′ ij ) ij∈E , H, previous_cost, V, (r ij ) ij∈E , (
∈ {i -1, i, i + 1, i + 2} do 9 saving ← r H i ,H i+1 + r H j ,H j+1 -r H i ,H j -r H i+1 ,H j+1 if H i ∈ V then saving ← saving + r ′ H i-1 ,H i+1 -r ′ H i-1 ,H j if H j ∈ V then saving ← saving + r ′ H j-1 ,H j+1 -r ′ H i ,H j-1 if H i+1 ∈ V then saving ← saving + r ′ H i ,H i+2 -r ′ H i+2 ,H j+1 if H j+1 ∈ V then saving ← saving + r ′ H j ,H j+2 -r ′ H i+1 ,H j+2 if saving > 0 then new_cost ← new_cost -saving
Replace edges x i,i+1 and x j,j+1 by x i,j and x i+1,j+1 in H Set the following backup edges variables to zero: We use Julia v1.8.5, JuMP v1.10.0, and Gurobi v10.0.1 to solve all linear programs and integer linear programs. Gurobi is used with default settings, except for the number of threads which is set to four, and PreCrush which is set to one, to enable user cuts in the B&BC algorithm. We enforce a time limit of one hour per instance. The computer used to carry out the computational experiments is equipped with an Intel(R) Core i7-7700 processor running at 3.60 GHz and 16

x ′ i-1,i+1 , x ′ i,i+2 , x ′ j-1,
GBytes of RAM, under GNU/Linux. which is also the number of times the subproblem is solved.

Each line in Table 2.3 presents an instance with the format "Instance name nα" where n is the total number of nodes in the instance and α is the aforementioned parameter. For Table 2.4, the format is "Class II n.ID" where ID varies from 1 to 5 and corresponds to the 5 randomly generated instances.

It can be seen in Table 2.3 that for Class I instances, the ILP model runs out of memory for 17 instances when the number of nodes exceeds 150, whereas this happens only once for the instance d 198-7 with the Branch-and-Benders-cut algorithm. The upper bound returned by the Branch-and-Benders-cut algorithm is always less than or equal to the one returned by ILP. The gap is better for the Branch-and-Benders-cut algorithm on 63 instances out of 95, and the lower bound is better for the Branch-and-Benders-cut algorithm on 30 instances out of 95. When an algorithm runs out of memory, we consider the other one to be better for LB, UB, and the gap. No comparison can be made for the instance d 198-7 as both algorithms run out of memory. From these observations, we conclude that Branch-and-Benders-cut tends to produce better quality solutions, while ILP tends to return better lower bounds (except for α = 3). The Branch-and-Benderscut algorithm has fewer memory issues than the ILP model on larger instances.

As expected, the number of explored nodes in the solver's branch-and-bound tree is significantly less with the ILP due to its size. The Branch-and-Benders-cut algorithm has always a better gap than the ILP model when α = 3, which suggests that it is more efficient when edge costs are relatively low. On the opposite, when α = 7, ILP returns a better gap except when memory issues occur, and for instances pr 136-7 and pr 152-7. It can also be observed that the CPU time spent solving Benders subproblems increases with α at a much faster pace than the number of optimality cuts. Indeed, the computational effort required to solve the Benders subproblem is larger when the ring has a low number of hubs. This is because there are a lot of terminals to assign to the (small) ring and the running time of the algorithm that solves the subproblem increases quadratically with the number of terminals. Not surprisingly, we also observe that for α = 3, the best available solutions have very few terminals, because of relatively large star costs. Table 2.4 reports results on Class II instances, for which ILP finds an optimal solution to seven small instances. The average value of the integrality gap of ILP in these instances is 1.29 with a standard deviation of 0.05. This relatively large integrality gap suggests that the problem formulation may be improved, independently of the subtour elimination constraints, that do not need to be added in large number for these instances. On Class II instances, the Branch-and-Benderscut model is much less efficient than ILP for small values of n, however, ILP shows memory difficulties for all instances with 150 nodes and more while the Branchand-Benders-cut model succeeds in obtaining solutions. We observe that for small instances, the number of optimality cuts varies a lot from one instance to another even if they have the same characteristics, see for example Class II -20. The same happens with the CPU time and the number of nodes in the branch-and-bound tree. For the remaining instances of Table 2.4, the number of optimality cuts seems homogeneous but this is just because the time limit is the same for all instances and they are not solved to optimality. So the number of optimality cuts that are reported corresponds to the number of cuts that have been generated in one hour, but the total number of cuts needed to obtain an optimal solution may vary significantly from one instance to the next for the same value of n.

In Table 2.5, six instances of Class I and six instances of Class II are solved without 2-opt backup, and the variation of the results with respect to those obtained with 2-opt backup in Tables 3.1 and 2.4 are displayed. When no solution improving over the one returned by the brute-force algorithms is found, 2-opt backup is not called and the results remain the same as in Tables 3.1 and 2.4. This happens for eil 51-7, pr 124-3, pr 124-5, and pr 124-7. It can be seen that for ClassII -20.1, the only instance solved to optimality, 2-opt backup is detrimental to the CPU time of ILP, but beneficial to the running time of the Branch-and-Benders-cut algorithm. The optimality gap of the ILP is generally increased when 2-opt backup is not used, and the effect is even more significant for Benders. When no time is consumed by 2-opt backup, the solver runs out of memory in less than one hour with instance ClassII -125.1 while it does not have enough time to saturate all the memory when 2-opt backup is used. The effect of 2-opt backup on the lower bound seems to be slightly detrimental for large instances, but improves the upper bound very significantly, especially in the case of the Branch-and-Benders-cut algorithm.

Chapter's structure

This chapter is structured as follows: in Section 3.3 we introduce the RESILIENT RING STAR PROBLEM and present an ILP formulation in Section 3.4. We describe a Branch-and-Benders-cut approach in Section 3.5. Numerical experiments are carried out for the two aforementioned approaches in Section 3.6. Finally, in Section 3.7, we address the question of determining which of the two strategies leads to the smallest cost, as a function of the failures duration.

Resilient Ring Star Problem definition

The Ring part aims to select a subset H ⊆ V and link up all hubs of H with a cycle using edges of E. The cost of opening a hub i ∈ V is d i ∈ R + and the cost of selecting an edge ij ∈ E between two hubs i and j is c ij ∈ R + .

The Star requires that each terminal in T = V \ H must be connected to exactly one hub in H. The cost of selecting an arc (i, j)

∈ A to connect a terminal i ∈ T to a hub j ∈ H is d ij ∈ R + .
The resilient ring-star network is designed so that when a hub h ∈ V fails, two corrective operations occur:

• The Ring correction consists in restoring the ring by adding a backup edge that joins the two neighbors of the failed hub h. The cost of selecting a

backup edge ij ∈ E is c ′ ij ∈ R + .
• The Star repair operation is to connect the terminals that were originally connected to the failing hub to another hub with backup arcs. The cost of selecting a backup arc (i, j)

∈ A ̸ = is d ′ ij ∈ R + where A ̸ = = {(i, j) ∈ A| i ̸ = j}.
For the rest of this document we will use the following notations: For a set of

nodes S ⊆ H, E(S) = {ij ∈ E| (i, j) ∈ S 2 }, E(S)
is the set of all edges of E having both their endpoints in S. For a node i ∈ V, δ(i) = {ij| ij ∈ E} is the set of all edges incident to i.

A MILP formulation for Resilient RSP

We consider the case where k = 1 and let F ∈ R + be the total duration of failures where a failure is a state when an uncertain hub is down. The 1-R-RSP can be formulated as a MILP described below. We will adapt the st-chains formulation for RSP given by Kedad-Sidhoum and Nguyen to 1-R-RSP. In particular, we set s = v 1 because 1 is the depot. We also add a dummy node t, a clone of the depot s in G to obtain a new graph

G ′ = (V ′ , E ′ ∪ A ̸ = ) where V ′ = V ∪ {t}, E ′ = E ∪ {st} ∪ {tu|su ∈ E}. We note J = {(i, j, k) ∈ V × V × V ′ : i ̸ = j, j ̸ = k, i < k}.
The following decision variables are used.

The binary variable x ij , ∀ij ∈ E ′ is such that x ij = 1 if edge ij is selected as a regular edge for connecting hubs i and j. The binary variable y ij , ∀(i, j) ∈ A ̸ = is such that y ij = 1 if arc (i, j) is selected as a regular arc for connecting terminal i to hub j. The binary variable y ii , ∀i ∈ V ′ is such that

y ii = 1 if node i is selected as a hub. The binary variable x ′ ij , ∀ij ∈ E ′ is such that x ′ ij = 1 if
edge ij is selected as a backup edge between hubs i and j. The binary variable y

′ ij ∈ B, ∀(i, j) ∈ A ̸ = is such that y ′ ij = 1 if arc (i, j)
is selected as a backup arc between terminal i to hub j.

There are also two other decision variables, θ ij ∈ R + , ∀(i, j) ∈ V × V, i ̸ = j which is an upper bound on the cost of the re-connection of terminal i ∈ T to the ring when hub j ∈ V fails and B ∈ R + which is the maximum total cost per unit of time incurred by re-connecting the terminals to the ring when the hub they are regularly connected to fails and fixing the ring by adding a backup edge in between two neighbors of the failing hub.

Constraints

Ring constraints (3.1) The ring must be made of at least four hubs. Indeed, if the ring has 3 or less hubs, the number of surviving hubs upon failure of any of them does not leave enough hubs to reform a ring by adding a backup edge. This case is sorted out by a brute force algorithm.

(3.2) The selected edges in E must form a cycle while (3.3) prevent two or more distinct cycles. For all strict subset S of V having cardinality at most 1 2 |V|, the number of edges joining pairs of hubs in S must be strictly less than |S| (to avoid having a cycle) provided that at least one hub is selected in V \ S.

(3.4), (3.5) The depot and its clone must be connected.

(3.6) The depot is a hub and cannot by assigned to another node.

∑ i∈V y ii ≥ 4 (3.1) ∑ ij∈δ(i) x ij = 2y ii , ∀i ∈ V ′ \ {s, t} (3.2) x(δ(S)) ≥ 2 ∑ j∈S y ij , ∀S ⊂ V ′ \ {s, t}, ∀i ∈ S (3.3) ∑ i∈V\{s} x si = 1 (3.4) ∑ i∈V\{s} x it = 1 (3.5)
y ss = y tt = 1, y si = 0, ∀i ∈ V ′ \ {s, t} (3.6)

Star constraints

(3.7) A node is either selected as a hub or is a terminal and is connected to exactly one hub.

(3.8) If a terminal is connected to a hub, then this hub must be opened and the edge between the terminal and the hub must not be in the cycle.

∑ j∈V y ij = 1, ∀i ∈ V (3.7) y ij ≤ y jj -x ij , ∀(i, j) ∈ A ̸ = (3.8)

Backup constraints

(3.9) For a selected uncertain hub and its neighbors in the ring, the edge between those two last hubs is a backup edge.

(3.9 ′ ) If we consider that the depot can fail, we must select a backup edge between its two neighbors. These constraints can be removed if the depot is certain.

(3.10) Every terminal has a backup arc to recover from a failure only if it is connected to an uncertain hub.

(3.11) Whenever a backup arc joins a terminal to a hub, this hub should be opened and this arc can not be a regular arc (3.11 ′ ) There is at most one arc or edge between any two nodes i and j. In addition, j must be a hub if there is an edge or an arc from i to j. If we have (3.11 ′ ) then we can remove (3.11) and (3.8) in the ILP. This is not the case when the Benders decomposition is applied because we want the Master problem of the Benders decomposition to have classical RSP solutions.

x ij + x jk -1 ≤ x ′ ik , ∀(i, j, k) ∈ J (3.9) x si + x kt -1 ≤ x ′ ik , ∀(i, k) ∈ (V \ {s}) 2 , i < k (3.9 ′ ) ∑ (i,j)∈A ̸ = y ′ ij = 1 -y ii - ∑ j∈V\{ V∪{i}} y ij , ∀i ∈ V (3.10) y ′ ij ≤ y jj -y ij , ∀(i, j) ∈ A ̸ = (3.11) x ij + y ij + x ′ ij + y ′ ij ≤ y jj , ∀(i, j) ∈ A ̸ = (3.11 ′ )

Backup cost constraints

(3.12) Let i ∈ V be a terminal regularly connected to a hub j ∈ V. The existence of this regular connection in the solution leads to y ij = 1. The cost for reconnecting terminal i to another hub whenever hub j fails can be computed as:

max k∈V\{i,j} d ′ ik y ′ ik
Let θ ij be an upper bound on the cost of reconnecting terminal i to the ring when hub j ∈ V fails.

(3.13) Finally, the maximum cost incurred by the failure of any hub is B. The first term of the left hand side is the cost of fixing the ring by using the backup edge ik when hub j ∈ V fails. The second one is the cost of using backup arcs to reconnect the terminals to surviving hubs when h, the hub to which they were regularly connected to, fails

∑ k∈V\{i,j} d ′ ik (y ′ ik + y ij -1) ≤ θ ij , ∀(i, j) ∈ V × V \ {i} (3.12) c ′ ik (x ′ ik + x ij + x jk -2) + ∑ t∈V\{j} θ tj ≤ B, ∀(i, j, k) ∈ J (3.13)

Objective function

An optimal solution to 1-R-RSP should minimize the total cost which is the deployment cost: (selecting hubs, connecting them with the ring, and connecting terminals to the ring), plus an upper bound of the fixing cost, which is computed by assuming that the hub incurring the highest fixing cost fails for F units of time during the time horizon, i.e., minimize:

1. The cost of selecting hubs that will be part of the ring;

2. The cost of connecting all terminals to the ring with regular arcs;

3. The cost of regular edges to form the ring;

4. An upper bound of the fixing cost, which is computed by assuming that the hub incurring the highest fixing cost fails for F units of time during the time

horizon Minimize ∑ i∈V d i y ii + ∑ (i,j)∈A ̸ = d ij y ij + ∑ ij∈E ′ c ij x ij + FB
The mathematical model of 1-R-RSP is then given by the following MILP:

                                                                                                                                     Minimize ∑ i∈V d i y ii + ∑ (i,j)∈A ̸ = d ij y ij + ∑ ij∈E ′ c ij x ij + FB ∑ i∈V y ii ≥ 4 ∑ ij∈δ(i) x ij = 2y ii ∀i ∈ V ′ \ {s, t} x(δ(S)) ≥ 2 ∑ j∈S y ij ∀S ⊂ V ′ \ {s, t}, ∀i ∈ S ∑ i∈V\{s} x si = 1 ∑ i∈V\{s} x it = 1 y si = 0 ∀i ∈ V ′ \ {s, t} y tt = 1 y ss = 1 ∑ j∈V y ij = 1 ∀i ∈ V x ′ ik ≥ x ij + x jk -1 ∀(i, j, k) ∈ J x ′ ik ≥ x si + x kt -1 ∀(i, k) ∈ (V \ {s}) 2 , i < k y jj ≥ x ij + y ij + y ′ ij + x ′ ij ∀(i, j) ∈ A ̸ = 1 -y ii - ∑ j∈V\{ V∪{i}} y ij = ∑ (i,j)∈A ̸ = y ′ ij ∀i ∈ V ∑ k∈V\{i,j} d ′ ik (y ′ ik + y ij -1) ≤ θ ij ∀(i, j) ∈ V × V \ {i} c ′ ik (x ′ ik + x ij + x jk -2) + ∑ t∈V\{j} θ tj ≤ B ∀(i, j, k) ∈ J x ij ∈ B ∀ij ∈ E ′ x ′ ij ∈ B ∀ij ∈ E ′ y ij ∈ B ∀(i, j) ∈ A y ′ ij ∈ B ∀(i, j) ∈ A ̸ = θ ij ∈ R + ∀i ∈ V, ∀j ∈ V \ {i} B ∈ R +

Post-optimization procedure

After solving the MILP formulation of 1-R-RSP, we either have B = 0 or B > 0. The case where B = 0 occurs when all the hubs are certain, it is possible only when the number of certain nodes is at least three. The corresponding solution has a zero fixing cost because no hub can fail. If B > 0, then there exists at least one uncertain hub that incurs a maximum fixing cost when it fails. This hub is said to be critical, as it sets the numerical value of B. Non-critical uncertain hubs have a fixing cost that is strictly less than B, so there may be optimal solutions to 1-R-RSP in which some non-critical hubs have a non-minimum fixing cost. In order to avoid this, the post-optimization procedure described in Algorithm 5 is executed. It recomputes the value of all the θ decision variables, knowing y and y ′ , the numerical value of the y and y ′ variables in an optimal solution to the MILP formulation of 1-R-RSP.

For the sake of illustration, Figure 3.1 shows the nonzero x, y, x ′ and y ′ variables of an optimal solution to the MILP formulation of 1-R-RSP on a 10-node Algorithm 5: A post-optimization procedure that sets the θ variables to their minimum value

1 foreach i ∈ V do 2 foreach j ∈ V do 3 if y ij = 1 and i ̸ = j and j ∈ V then 4 k ← 1 5 while y ′ ik = 0 do 6 k ← k + 1 7 θ ij ← d ′ ik 8 else 9 θ ij ← 0
instance in which the depot is the only certain node. The x and y nonzero variables form a solution to RSP on that instance, it is shown in red. The plain blue edges are the backup edges. In particular, the backup edge (1,[START_REF] Ben-Tal | Robust convex optimization[END_REF] is used to fix the failure of hubs 3 and 10. The blue dashed arcs are the nonzero backup arcs in that solution. It can be seen than no backup arc is needed for terminals 5 and 9, as they are connected to a certain hub. All the other terminals are associated exactly one backup arc, to be used upon failure of the uncertain hub they are regularly connected to.

B = max c ′ 1,6 + d ′ 7,6 , c ′ 3,10 + d ′ 2,3 , c ′ 1,6 + d ′ 4,6 + d ′ 8,6 θ 2,6 ≥ d ′ 2,3 θ 4,10 ≥ d ′ 4,6 θ 7,3 ≥ d ′ 7,6 θ 8,10 ≥ d ′ 8,6
The value of B is the maximum over 3 quantities, that represent the cost incurred by the failure of hubs 3, 6 and 10 respectively. θ 2,6 is an upper bound on the cost of reconnecting terminal 2 when hub 6 fails. This cost may be strictly larger

than d ′ 2,3 if hub 6 is non-critical, as long as c ′ 3,10 + d ′ 2,
3 is strictly less than B.

A Branch-and-Benders-cut decomposition of 1-R-RSP

The complicating variables are x and y because when they are known in advance, the subproblem becomes easy to solve and consists of computing the worst-case repairing cost among each hub failure of the ring. This means that the master problem is to solve RSP which is a hard problem.

Master problem

In a regular Benders decomposition approach, (3.11') is in the subproblem, so the master problem would return solutions in which terminals may possibly be connected to some other terminals. Hence the solutions of the master problem are not RSP solutions, and may be overly relaxed. To avoid this, we add (3.8) in the master problem which guarantees that the solutions to the master problem are

solutions to RSP.                                                                                    Minimize ∑ i∈V d i y ii + ∑ (i,j)∈A ̸ = d ij y ij + ∑ ij∈E ′ c ij x ij + η ∑ i∈V y ii ≥ 4 ∑ ij∈δ(i) x ij = 2y ii ∀i ∈ V ′ \ {s, t} x(δ(S)) ≥ 2 ∑ j∈S y ij ∀S ⊂ V ′ \ {s, t}, ∀i ∈ S ∑ i∈V\{s} x si = 1 ∑ i∈V\{s} x it = 1 y si = 0 ∀i ∈ V ′ \ {s, t} y tt = 1 y ss = 1 ∑ j∈V y ij = 1 ∀i ∈ V y jj -x ij ≥ y ij ∀(i, j) ∈ A ̸ = x ij ∈ B ∀ij ∈ E ′ y ij ∈ B ∀(i, j) ∈ A η ∈ R +

Benders subproblem

Assuming that the complicating variables are given as input parameters x and y, the primal subproblem can be formulated as follows:

                                                   η = Minimize FB x ′ ik ≥ x ij + x jk -1 ∀(i, j, k) ∈ J ∑ (i,j)∈A ̸ = y ′ ij = 1 -y ii - ∑ j∈V\{ V∪{i}} y ij ∀i ∈ V θ ij -∑ k∈V\{i,j} d ′ ik y ′ ik ≥ ∑ k∈V\{i,j} d ′ ik ( y ij -1) ∀i ∈ V, ∀j ∈ V \ {i} B -c ′ ik x ′ ik -∑ t∈V\{j} θ tj ≥ c ′ ik ( x ij + x jk -2) ∀(i, j, k) ∈ J x ′ ij + y ′ ij ≤ y jj -x ij -y ij ∀(i, j) ∈ A ̸ = x ′ ij ∈ B (i, j) ∈ V × V ′ , i < j y ′ ij ∈ B ∀(i, j) ∈ A ̸ = θ ij ∈ R + ∀i ∈ V, ∀j ∈ V \ {i} B ∈ R +
Moreover, this integer linear program is easy to solve, and the optimal objective value is B( x, y) = 0 if the set {j : j ∈ V, y jj = 1} is empty, otherwise:

B( x, y) = min (i,j,k)∈ J x ij = x jk =1      c ′ ik + ∑ i ′ ∈V\{j} y i ′ j =1 min k ′ ∈V\{j} y k ′ k ′ =1 d ′ i ′ k ′     
A feasible solution to this integer linear program can be built as follows:

• x ′ ij is initialized to zero for all (i, j) ∈ A ̸ = .

• If ∑ i∈V y ii = 4, let s, a, b, c, t be the st-chain that represents the ring. If s ∈ V or b ∈ V, then set x ′ ac to one. If a ∈ V or c ∈ V, then set x ′ sb to one.

• Otherwise, i.e., ∑ i∈V y ii ≥ 5, then for all (i, j, k) ∈ J, if

x ij = x jk = 1, then x ′ ik is set to one.
• For all i ∈ V such that y ii = 1, i.e., node i is a hub, there is no backup arc leaving i, so y ′ ij is set to zero for all j ∈ V\{i}, and θ ij is set to zero for all j ∈ V\{i}.

• For all i ∈ V such that y ii = 0, i.e., node i is a terminal, there exists a unique hub j ∈ V\{i} such that y ij = 1. One of the following two sub-cases applies:

-If j ∈ V\( V ∪ {i}), i.e., node j is a certain hub, then j cannot fail and there is no backup arc leaving i, so y ′ ik is set to zero for all k ∈ V\{i}, and θ ik is set to zero for all k ∈ V\{i}.

-If j ∈ V\{i}, i.e., node j is an uncertain hub, let k be a hub such that

d ′ ik = min q∈V\{j} y qq =1 d ′ iq , hence y ′
ik is set to one, and y ′ iq is set to zero for all q ∈ V\{i, k}. Also, θ ij is set to d ′ ik as this is the cost incurred by reconnecting terminal i to hub k when hub j fails, and θ iq is set to zero for all q ∈ V\{i, j}. Now, we consider the LP-relaxation of the primal of the Benders subproblem, where the upper bound on x ′ and y ′ are relaxed, because there exists an optimal solution to this LP that satisfies them:

                                                   η = Minimize FB ∑ (i,j)∈A ̸ = y ′ ij = 1 -y ii - ∑ j∈V\{ V∪{i}} y ij ∀i ∈ V [α i ] x ′ ik ≥ x ij + x jk -1 ∀(i, j, k) ∈ J [β ijk ] θ ij -∑ k∈V\{i,j} d ′ ik y ′ ik ≥ ∑ k∈V\{i,j} d ′ ik ( y ij -1) ∀i ∈ V, ∀j ∈ V \ {i} [γ ij ] B -c ′ ik x ′ ik -∑ t∈V\{j} θ tj ≥ c ′ ik ( x ij + x jk -2) ∀(i, j, k) ∈ J [δ ijk ] -x ′ ij -y ′ ij ≥ x ij + y ij -y jj ∀(i, j) ∈ A ̸ = [ϵ ij ] x ′ ij ≥ 0 ∀ij ∈ E ′ y ′ ij ≥ 0 ∀(i, j) ∈ A ̸ = θ ij ≥ 0 ∀i ∈ V, ∀j ∈ V \ {i} B ≥ 0
The dual of this linear program is

                                                                                           η = Maximize ∑ i∈V   1 -y ii - ∑ j∈V\{ V∪{i}} y ij   α i + ∑ (i,j,k)∈ J ( x ij + x jk -1)β ijk + ∑ (i,j)∈V× V\{i}   ∑ k∈V\{i,j} d ′ ik ( y ij -1)   γ ij + ∑ (i,j,k)∈ J c ′ ik ( x ij + x jk -2)δ ijk + ∑ (i,j)∈A ̸ = ( x ij + y ij -y jj )ϵ ij ∑ (i,j,k)∈ J β ijk -c ′ ik δ ijk -ϵ ik -ϵ ki ≤ 0 ∀(i, k) ∈ V × V, i < k [x ′ ik ] ∑ (i,j,t)∈ J β ijt -c ′ it δ ijt ≤ 0 ∀i ∈ V [x ′ it ] ∑ (i,j,k)∈ J δ ijk ≤ F [B] α i -d ′ ij ∑ k∈ V\{i,j} γ ik -ϵ ij ≤ 0 ∀i ∈ V, ∀j ∈ V\{i} [y ′ ij ] γ ij -∑ (q,j,k)∈ J δ qjk ≤ 0 ∀i ∈ V, ∀j ∈ V \ {i} [θ ij ] α i ∈ R ∀i ∈ V β ijk ≥ 0 ∀(i, j, k) ∈ J γ ij ≥ 0 ∀(i, j) ∈ V × V\{i} δ ijk ≥ 0 ∀(i, j, k) ∈ J ϵ ij ≥ 0 ∀(i, j) ∈ A ̸ =
We propose an optimal solution to the dual, that is built as shown in Algorithm 7. To compute this solution, we need to determine the critical triplet (i ⋆ , j ⋆ , k ⋆ ) ∈ J such that x i ⋆ j ⋆ = x j ⋆ k ⋆ = 1, and

c ′ i ⋆ k ⋆ + ∑ i∈V\{j ⋆ } y ij ⋆ =1 min k∈V\{j ⋆ } y kk =1 d ′ ik = min (i,j,k)∈ J x ij = x jk =1      c ′ ik + ∑ i ′ ∈V\{j} y i ′ j =1 min k ′ ∈V\{j} y k ′ k ′ =1 d ′ i ′ k ′     
This is achieved by Algorithm 6. The solution returned by Algorithm 7 is feasible for the dual, and the corresponding objective value is c

′ i ⋆ k ⋆ + ∑ i∈V\{j ⋆ } y ij ⋆ =1 min k∈V\{j ⋆ } y kk =1 d ′ ik ,
i.e., it is the same as the one of the LP relaxation of the primal, and also the same as the one of the integer linear programming formulation of the Benders subproblem, which proves that both these solutions are optimal.

Benders optimality cut

The objective function of the dual of the subproblem is

η = ∑ i∈V   1 -y ii - ∑ j∈V\{ V∪{i}} y ij   α i + ∑ (i,j,k)∈ J ( x ij + x jk -1)β ijk + ∑ (i,j)∈V× V\{i}   ∑ k∈V\{i,j} d ′ ik ( y ij -1)   γ ij + ∑ (i,j,k)∈ J c ′ ik ( x ij + x jk -2)δ ijk + ∑ (i,j)∈A ̸ = ( x ij + y ij -y jj )ϵ ij
The solution of the dual of the LP relaxation is used and in the master problem, we should add the optimality cut:

η ≥ ∑ i∈V\{j ⋆ } y ij ⋆ =1   1 -y ii - ∑ j∈V\{ V∪{i}} y ij     F min k∈V\{i,j ⋆ } y kk =1 d ′ ik    +(x i ⋆ j ⋆ + x j ⋆ k ⋆ -1) Fc ′ i ⋆ k ⋆ + ∑ i∈V\{j ⋆ } y ij ⋆ =1   ∑ k∈V\{i,j ⋆ } d ′ ik (y ij ⋆ -1)   F +c ′ i ⋆ k ⋆ (x i ⋆ j ⋆ + x j ⋆ k ⋆ -2)F + ∑ i∈V\{j ⋆ } y ij ⋆ =1               ∑ j∈V\{i} y jj =0 min k∈V\{i,j ⋆ } y kk =1 d ′ ik > d ′ ij   F • min k∈V\{i,j ⋆ } y kk =1 d ′ ik -F • d ′ ij    x ij + y ij -y jj +   F • min k∈V\{i,j ⋆ } y kk =1 d ′ ik    x ij ⋆ + y ij ⋆ -y j ⋆ j ⋆              
Since η = FB, we can simplify this optimality cut to

B ≥ ∑ i∈V\{j ⋆ } y ij ⋆ =1   1 -y ii - ∑ j∈V\{ V∪{i}} y ij      min k∈V\{i,j ⋆ } y kk =1 d ′ ik    +(2x i ⋆ j ⋆ + 2x j ⋆ k ⋆ -3)c ′ i ⋆ k ⋆ + ∑ i∈V\{j ⋆ } y ij ⋆ =1 ∑ k∈V\{i,j ⋆ } d ′ ik (y ij ⋆ -1) + ∑ i∈V\{j ⋆ } y ij ⋆ =1               ∑ j∈V\{i} y jj =0 min k∈V\{i,j ⋆ } y kk =1 d ′ ik > d ′ ij    min k∈V\{i,j ⋆ } y kk =1 d ′ ik -d ′ ij    x ij + y ij -y jj +    min k∈V\{i,j ⋆ } y kk =1 d ′ ik    x ij ⋆ + y ij ⋆ -y j ⋆ j ⋆               B ≥ ∑ i∈V\{j ⋆ } y ij ⋆ =1   1 -y ii + x ij ⋆ + y ij ⋆ -y j ⋆ j ⋆ - ∑ j∈V\{ V∪{i}} y ij      min k∈V\{i,j ⋆ } y kk =1 d ′ ik    +(2x i ⋆ j ⋆ + 2x j ⋆ k ⋆ -3)c ′ i ⋆ k ⋆ + ∑ i∈V\{j ⋆ } y ij ⋆ =1 ∑ k∈V\{i,j ⋆ } d ′ ik (y ij ⋆ -1) + ∑ i∈V\{j ⋆ } y ij ⋆ =1 ∑ j∈V\{i} y jj =0 min k∈V\{i,j ⋆ } y kk =1 d ′ ik > d ′ ij    min k∈V\{i,j ⋆ } y kk =1 d ′ ik -d ′ ij    x ij + y ij -y jj
Note that now, the objective function of the master problem is exactly the same as the one of the MILP formulation (η has been replaced by FB), which implies that η is no longer a decision variable of the master problem. Instead, B is now part of the complicating variables, and is a decision variable of the master problem.

Algorithm 7 runs in cubic time because of the initialization phase (there is a cubic number of β ijk variables for instance). But if we ignore initialization, the running time of Algorithm 7 is simply quadratic. So now, we can argue that the Benders optimality cut can be separated in quadratic time because:

• The last expression of the Benders optimality cut has at most two nested sums, so it requires to add O(n 2 ) terms.

• What we need to build this optimality cut are the non-zero dual variables only, so we can drop the initialization phase of Algorithm 7, in practice. This is due to the fact that a unique β ijk variable has a non-zero value (same thing for δ ijk ), this is the key for "killing" the cubic factor.

By contrast, the separation of the original Benders optimality cut requires making the sum of a cubic number of terms (the fact that the cardinality of J is in O(n 3 ) is sufficient to show it). So we have an efficient separation algorithm based upon the computation of the critical triplet (in quadratic time), and Algorithm 7 which is quadratic also provided we skip the initialization phase.

Numerical Experiments

The ILP introduced in Section 3.4 as well as the Branch-and-Benders cut decomposition algorithm in Section 3.5, are implemented with the post-procedure optimization described in Subsection 3.4.1 and tested on a set of TSPLIB instances.

Similarly to Section 2.7, these TSPLIB instances are a collection of 32 × 3 × 4 = 384 TSP instances involving between 51 and 200 nodes. Let l ij be the Euclidian distance between nodes i and j of V, we define the ring cost by c ij = ⌈αl ij ⌉ and the star cost by d ij = ⌈(10 -α)l ij ⌉ where α is in the set {3, 5, 7}, for all (i, j) in V 2 . c ′ ij is set to 0.01c ij and is a cost per day in a one-year time horizon. d ′ ij is set to 0.01d ij and is also a cost per day in a one-year horizon. Opening costs are zero for these instances. F is expressed in days, set to 4 values, F = 0 which means there is no failures, F = 7 which is one week, F = 31 (one month) and F = 183 (6 months).

We use Julia v1.8.0, JuMP v1.2.1 and Gurobi v9.0.3 to solve all integer and linear programs. The same settings for Gurobi as in Section 2.7 are used. We enforce a time limit of one hour per instance. The computer used to run the numerical experiments is a DELL equiped with a Intel(R) Core(TM) i7-10610U CPU @ 1.80GHz and 16GBytes of RAM, under GNU/Linux. Table 3.1 present the results for the TSPLIB class. Two methods are tested, the ILP mentioned in Section 3.4 and the Branch-and-Benders scheme mentioned in Section 3.5. The columns of this table are as follows: F is the aforementioned parameter, it is the total duration of failures in days, CPU is the total CPU time in seconds, it includes the Brute Force Algorithm 1 CPU times which can be adapted for Resilient RSP. "TL" is indicated when the time limit of one hour is reached; Gap represents the relative optimality gap of both methods. Its formula is the same as in Table 2.2. Both LB and UB are also displayed in Table 3.1; |H| is the number of hubs in the best solution found. Note that since there is a single certain node in the considered instances, Algorithm 1 cannot find any ring with three hubs. n_subtour is the number of subtour elimination constraints, i.e., feasibility cuts for Benders, and lazy constraints for ILP.

Columns Nodes show the total number of explored nodes in the solver's branchand-bound tree during the search. CPU SP is the CPU time in seconds for solving the Benders subproblems. n_cut gives the number of optimality cuts in the Benders decomposition, which is also the number of times the subproblem is solved.

Each line in Table 3.1 presents an instance with the format "Instance name n -α" where n is the total number of nodes in the instance and α is the aforementioned parameter. Some instances does not appear in Table 3.1, these are the instances where both ILP and Branch-and-Benders-cut algorithm run out of memory. When "NO SO-LUTION FOUND" is printed, that means the algorithm could not find a solution within the one hour time limit. We noticed that ILP finds a valid solution without going out of memory on 64 out of 384 instances while Branch-and-Benders-cut algorithm finds a valid solution without going out of memory on 95 instances out of 384 instances. That means the Branch-and-Benders-cut algorithm is able to find solutions more often than the ILP model. Moreover, considering that an algorithm is better than another when both gaps are 0% and its CPU is lower or both gap or greater than 0% but its gap is lower then, when F = 0 (no failures), the Branch-and-Benders-cut algorithm is better on 13 instances while the ILP is better on three instances. When F = 7 (one week), the Branch-and-Benders-cut al-gorithm is better on 31 instances while the ILP is better on three instances. When F = 31 (one month), the Branch-and-Benders-cut algorithm is better on 23 instances and the ILP is better on 6 instances. When F = 183 (six months), the Branch-and-Benders-cut algorithm is better on 11 instances and the ILP is better on 9 instances. We observe that the easiest instances for the Branch-and-Benderscut are the ones with lower F, except for F = 0 (no failures). Moreover, when both algorithms find an optimal solution, the CPU times tend to be from 2 times faster up to 15 times faster for the Branch-and-Benders-cut algorithm. We observe that among the values of the parameter α, the easiest instances to solve are the ones with α = 3 for the Branch-and-Benders-cut algorithm. We also observe that no instances with more than 105 nodes (lin-105) can be solved within the time limit for the Branch-and-Benders-cut algorithm while the ILP cannot solve instances bigger than 76 nodes (pr-76).

Resilient or Survivable Ring Star Problem?

In Chapter 2, we studied a Survivable variant of the Ring Star Problem and in Chapter 3 a Resilient variant of the same problem. In this subsection, we address the question of determining which of the two strategies leads to the smallest cost, as a function of the failures duration.

Properties

It is shown in this section that g(F), the function that associates the optimal objective function value of 1-R-RSP(F) as a function of F, is continuous piecewise linear and concave.

For all F ≥ 0, we denote by σ(F) the set of all the optimal solutions to 1-R-RSP(F). The objective value of any feasible solution S to 1-R-RSP(F) can be written as K S + FB S , where

K S = ∑ ij∈E ′ c ij x ij + ∑ (i,j)∈A ̸ = d ij y ij + ∑ i∈V d ii y ii and B S = B are nonnegative constants. For all F 0 ≥ 0, an optimal solution S F 0 to 1-R-RSP(F 0 ) is said to be B-optimal for 1-R-RSP(F 0 ) if it is such that B S F 0 = min S∈σ(F 0 ) B S .
Observation 1: If solution S F 0 is B-optimal for 1-R-RSP(F 0 ), then for all S ∈ σ(F 0 ), we have K S F 0 + F 0 B S F 0 = K S + F 0 B S . By definition of a B-optimal solution, we have B S F 0 ≤ B S for all S ∈ σ(F 0 ). So adding B S F 0 (F -F 0 ) ≤ B S (F -F 0 ) to the last equality yields K S F 0 + FB S F 0 ≤ K S + FB S for all F ≥ F 0 .

Lemma: For all F 0 ≥ 0, there exists ε > 0 such that any B-optimal solution S F 0 to

F 0 B 0 S 0 F 1 B 1 S 1 F 2 B 2 S 2 F 3 B 3 S 3 K 0 K 1 K 2 K 3 F g(F)
Figure 3.2: Illustration of the shape of g(F) with q = 4 Property 3: Let F 0 < F 1 . Let S 0 (resp. S 1 ) be an optimal solution to 1-R-RSP(F 0 ) (resp. 1-R-RSP(F 1 )). If B S 0 = B S 1 , then S 0 is an optimal solution to 1-R-RSP(F) for all F ∈ [F 0 , F 1 ].

Proof: Property 3 is the consequence of the fact that g(F) is concave. Indeed, for all F ∈ (F 0 , F 1 ), the optimal solution S F to 1-R-RSP(F) is such that g

(F) = K S F + FB S F , with B S 0 ≤ B S F ≤ B S 1 . Since B S 0 = B S 1 , we have B S F = B S 0 for all F ∈ [F 0 , F 1 ], hence S F = S 0 .

Computational method to solve 1-R-RSP(F) on an interval

We wish to find an optimal solution to 1-R-RSP(F) for all F ∈ [F ℓ , F r ]. But we wish to avoid determining B-optimal solutions to 1-R-RSP, because this may be costly.

In the sequel, if S is a solution to 1-R-RSP(F), S.B denotes the associated value of B, and S.K denotes K S .

• Solve 1-R-RSP(F ℓ ), and obtain solution S ℓ (so B S ℓ ← S ℓ .B, and

K S ℓ ← g(F ℓ ) -F ℓ B S ℓ = S ℓ .K are known)
• Solve 1-R-RSP(F r ), and obtain solution S r (so B S r ← S r .B, and K S r ← g(F r ) -F r B S r = S r .K are known)

• Store (F ℓ , S ℓ )

• Store (F r , S r )

• Explore the interval [F ℓ , F r ] by calling EXPLORE(F ℓ , S ℓ , F r , S r ). This function recursively splits the interval to determine the different line segments of and the pair (F ℓ , S ℓ ) is stored. Now, we assume that F m is in (F ℓ , F r ), and we compute S m , an optimal solution to 1-R-RSP(F m ).

If K S ℓ + F m B S ℓ = K S m + F m B S m
(see Figure 3.4, left), then we know that solution S ℓ is an optimal solution to 1-R-RSP(F) for all F ∈ [F ℓ , F m ] by Property 3, hence we store the pair (F m , S r ).

If K S ℓ + F m B S ℓ > K S m + F m B S m (see
F ℓ g(F ℓ ) F r g(F r ) F Obj. val. F ℓ = F m g(F ℓ ) F r g(F r ) F Obj. val. F ℓ g(F ℓ ) F r = F m g(F r ) F Obj. val. B S ℓ = B S r F m = F ℓ F m = F r Figure 3.3:
Illustration of the situations that can occur when EX-PLORE(F ℓ , S ℓ , F r , S r ) is run

F ℓ g(F ℓ ) F r g(F r ) F m g(F m ) F Obj. val. F ℓ g(F ℓ ) F r g(F r ) F m g(F m ) F Obj. val. K S ℓ + F m B S ℓ = K S m + F m B S m K S ℓ + F m B S ℓ > K S m + F m B S m Figure 3.4: Illustration of the situations that can occur when F m ∈ (F ℓ , F r ) in EX- PLORE(F ℓ , S ℓ , F r , S r ) S 0 S 1 S 2 S 3 F g(F) f 1-S-RSP F ⋆ Figure 3.5:
Comparing the optimal solutions of 1-R-RSP(F) and 1-S-RSP F ⋆ = 569.76 and Survivable RSP above. We see in Table 3.2 that the number of optimal solutions |S i | is equal to the number of F values. This means that the proposed approach is efficient in the sense that we solve the minimum number of instances of 1-R-RSP(F). Figures 3.6, 3.7, 3.8, 3.9 and 3.10 show the 5 solutions S i , i ∈ {1, . . . , 5} for the instance of 10 nodes. The critical hub which incurs the worst-case repairing cost among each hub failure of the ring is represented in green as well as its corresponding backup edge and the decision variable B. As expected, solution S 1 has a low cost when F = 0, but this cost increases significantly with F. Symmetrically, solution S 5 has a large cost, but it increases at a slow pace when F increases.

Conclusions

Overview

In this thesis, we introduced a survivable and a resilient variant of the Ring Star Problem. The survivable variant called 1-S-RSP reduces to RSP when there are no uncertain nodes and is shown to be much harder to solve when the cardinality of the uncertain nodes grows. We introduced an ILP formulation to address this problem as well as a Branch-and-Benders-cut algorithm. We improved both ILP and Branch-and-Benders-cut and in particular, generalized the 2-opt heuristic from the traveling salesman problem to deal with uncertain hubs. We

Limitations

For the Resilient variant of RSP, the Branch-and-Benders-cut scheme and the ILP can be improved. The Branch-and-Benders-cut scheme does not have an instance transformation for its master problem and both models do not take advantage of a 2-opt heuristic adapted method. As a result, instances of more than 105 nodes are not solved by the Branch-and-Benders-cut scheme. Extensive numerical experiments should be carried out to deepen the analysis of the analysis of these early results. Regarding the solution of 1-R-RSP(F) for all F, it is applicable only to small instances for which 1-R-RSP(F) can be solved to optimality in a reasonable amount of time. In addition, even if we know that the number of linear pieces in g(F) is finite (because the number of distinct solutions to RSP is finite), determining the number of linear pieces of g(F) is still an open question.

Future works

The following future work directions may be considered promising. First, any feasible solution found by ILP may be attempted for improvement by solving the subproblem of the Branch-and-Benders-cut algorithm. Moreover, other existing heuristic approaches may be used to try to improve the ring by changing some hubs, not just the edges that join them. In the same vein, existing heuristics or metaheuristics could be extended to 1-S-RSP and used to warm start ILP and the Branch-and-Benders-cut model. We could also develop heuristics for large instances. A more challenging research direction consists in searching for a fast way to generate optimality cuts before solving the Branch-and-Benders-cut model. Such valid inequalities may be obtained from feasible solutions to 1-S-RSP, but not all of them are useful. Another promising future work direction would be to decompose the subproblem of 1-S-RSP to |V \ H| + 1 subproblems and solve the dual for each of them. That would lead to |V \ H| + 1 optimality cuts that could be of better quality than the single optimality cut added in the Branch-and-Benders-cut algorithm presented in this thesis. Second, it may be relevant to adapt the st-chains formulation introduced in [START_REF] Kedad-Sidhoum | An exact algorithm for solving the ring star problem[END_REF] for RSP to 1-S-RSP. This st-chains formulation has been adapted for 1-R-RSP in this thesis but the blossom inequalities have not been exploited. When we cannot afford to solve 1-R-RSP(F) many times, how can we estimate F ⋆ ? A research direction may be to store and transfer all the subtour constraints (for the ILP model) and all the optimality cuts (for the Branch-and-Benders-cut scheme) to the next 1-R-RSP solution. We could also use a 1-R-RSP solution for the closest values of F to warm-start the solving process.

As shown in Table 2.2, the extra cost required to offer survivability is very large, which means that the proposed solution is adapted to situations where the failure of a hub is frequent. If it is not the case, it may be more relevant to favor solutions that are easy or inexpensive to fix. Finally, a natural research direction is to consider the situation where more than one hub can fail in both variants. For

  -cut exact methods for two fault-tolerant Ring Star problem variants", prolonge le chemin entrepris depuis ce premier ordinateur à écran cathodique que mon père m'a fait découvrir à quatre ans." Julien Khamphousone Dedicated to Shagana Mary Progam • M. Azeba [3e A, Mathematics] (2010-2011) (French and English) Lycée Guillaume Apollinaire, Thiais (94) • Mme Castano [2de générale, Physics and Chemistry] (2011-2012) • Mme Grosol [2de générale, English] • M. Filey [2de générale, Mathematics] • Mme Wong [1re S1-SI, Mathematics] • Mme Chauvin [1re S1-SI, Physics and Chemistry] • Mme Bonneron [1re S1-SI, English] (2012-2013) Lycée Lakanal, Sceaux (92) • Mme Proix, [Tle S, Physics and Chemistry] (2013-2014) • M. Leterrier, Agrégation jury member [Tle S, Mathematics] Lycée Paul Valéry, Paris 12e • Dr. Chloé Mullaert [Mathematics] (2014-2015, MPSI) • Dr. Gael Benabou [Mathematics] (2015-2016, MP) Top French Engineering School ENSIIE, Évry • Dr. Dimitri Watel [Computer Science] (2016-2019) • Dr. Alain Faye [Computer Science] (2016-2019) Conservatoire National des Arts et Métiers, Paris 3e • The Master Parisien de Recherche Opérationnelle (MPRO) Professorship [Operations Research] (2018 -2019) Université Paris Dauphine, Paris 16e • Pr. Jérôme Lang, [Operations Research and Artificial Intelligence] (2023) • The (French) Laboratoire d'Analyse et de Modélisation de Systèmes pour l'Aide à la Décision (LAMSADE) researchers Family Jeannie Lao, grandmother, Martin Lao, grandfather, Virginie Lao, mother, Pang Khamphousone, father, Manivanh Khamphousone, grandmother, Oudone Khamphousone, grandfather, Alicia Khamphousone, younger sister. My five uncles and two aunties: Éric Lao, Saly Ly, adopted, Hélène Panyanouvath, Jacques Khamphousone, Somchit Khamphousone, Padit Khamphousone, Mouang Khamphousone My cousins and in particular Andy Panyanouvath and Pranavong Khamphousone. Kiwi Khamphousone, a little like my young brother, my cat and my love for biology. Healthcare • Dr. Pascale Romain, general practitioner • Dr. Guillaume Laperrousaz, Confidential • Dr. Isaac Salem, Confidential • Dr. Georges Kill, Confidential • Dr. Olivier Confidential, virologist and CNRS researcher Future Shagana Progam and her family until the end of my life. Friends Pierre-François Villard (ENPC), qui a relevé un homme à terre pendant Dassault Systèmes. Dr. Ali Tlili (Dassault Systèmes), pour son humour si Ali ! Églantine Boucher (MPSI-MP comrade), pour m'avoir transmis l'importance de l'amitié. Séverine Bonnechère (MPRO comrade), Bastien Rolland (MPRO comrade), Victor Kani (MPRO comrade), Guillaume Crognier (MPRO comrade), impressionants en recherche opérationnelle, impressionants humainement. Toby Ratantely (NA-Motorsports and Orange), pour son aide, sa gentillesse et sa bienveillance. The NA-Motorsports community and the three FMWC titles, FMWC Individual (2021 and 2022) and FMWC Duo (2022).

Figure 1 .

 1 1 shows an example of such a network.

Figure 1 . 1 :

 11 Figure 1.1: Ring Star network

Figure 1 . 2 : 2 -

 122 Figure 1.2: 2-edge connected star, dual homed network[START_REF] Ekin Karaşan | Survivability in hierarchical telecommunications networks under dual homing[END_REF]

  (2016) have used an accelerated Benders decomposition to solve a hybrid robust and stochastic optimization for closedloop supply chain network design. Recently, Juvin et al. [30] (2023) studied the flexible job-shop scheduling problem, a generalization of the job-shop scheduling problem, and considered preemptible tasks for this generalization. They use a logic-based Benders decomposition to solve this problem.

Figure 1 .

 1 Figure 1.3 shows the framework for the classical Benders decomposition method with a flowchart. In this figure, SP( x) is the optimal objective value of the sub-

Figure 2 . 1 :

 21 Figure 2.1: An 11-node solution of the 1-S-RSP with V = V \ {1, 11}

Figure 2 . 2 : 1 -

 221 Figure 2.2: 1-S-RSP instance with V = {2, 3, 4} where the dashed backup edge is used when hub 2 or 4 fails.

2 3 7 y2,1 1 y 3 , 1 y 7 , 9 y 7 , 5 Figure 2 . 3 :

 7131797523 Figure 2.3: Nonzero variables for a solution to an 11-node instance of 1-S-RSP

Figure 2 . 4 :

 24 Figure 2.4: Branch-and-Benders-cut decomposition scheme

2 -

 2 opt backup, an extension of the classical 2-opt algorithm proposed by G.A.Croes[START_REF] Croes | A method for solving traveling-salesman problems[END_REF]. 2-opt backup is applied to both ILP and Branch-and-Benders-cut decomposition. It consists of improving the ring of the current solution by the mean of 2-opt backup moves. These moves differ from classical 2-opt moves as they also consider backup edges. Algorithm 4 describes the 2-opt backup procedure which takes as input argument the ring and backup edges x and x ′ as well as their associated costs r and r ′ , the array of hubs H that appear in the same order as in the ring, the cost of the input solution stored in previous_cost and V. We use H i for i ∈ {1, . . . , |H|} to denote the i-th element of H, that is H[i].

Figure 2 .

 2 5 illustrate a 2-opt backup move where the old backup edge

1 ringFigure 2 . 5 :

 125 Figure 2.5: Illustration of edges before (left) and after (right) a 2-opt backup move

Figure 2 . 6 :

 26 Figure 2.6: 4 optimal RSP solutions with the same instance except the ring and star costs for 4 values of input paramter α

  We study a Resilient variant of the Ring Star Problem named 1-R-RSP in which the failure of a node in a given subset of so-called uncertain nodes triggers two corrective operations to repair the Ring Star structure. We model this problem as an Integer Linear Program (ILP), that is also addressed with a Branch-and-Benders-cut decomposition. Several enhancements to both the ILP and Branchand-Benders-cut algorithm are also presented. We then compare the solutions of the resilient and survivable variants, in order to determine which variant is the most appropriate, as a function of failure frequency. This chapter's work has been presented in ROADEF 2021 and 2023.

Figure 3 . 1 :

 31 Figure 3.1: The nonzero x, x ′ , y and y ′ variables of a solution to 1-R-RSP

Figure 3 . 4 ,

 34 right), then solution S m has a slope B S m ∈ (B S ℓ , B S r ), so the interval [F ℓ , F r ] is halved, and the exploration is launched recursively on the intervals [F ℓ , F m ] and [F m , F r ].

  also introduce an instance transformation to enhance the master problem performance. Extensive numerical experiments have been carried out and the Branchand-Benders-cut is shown to have a better performance for instances with a large number of nodes. Both methods have been tested on instances up to 200 nodes.The second problem we introduced, Resilient RSP, was modeled with an ILP and a Branch-and-Benders-cut model similarly to the first problem, the performance of the Branch-and-Benders-cut is shown to be much better than the ILP, solving instances up to 105 nodes. The practical question of determining which approach to use as a function of the duration of the failures has also been addressed. RSP has been studied since 1998 and exact and heuristics methods have been developed for this problem. Resilience and Survivability are concepts studied in many fields including combinatorial optimization and in this thesis, we filled the gap in the RSP literature by the study of the resilient and the survivable variants.

  The master problem is denoted by MP, and is built by replacing the contribution of the y variables in the objective function of the original problem, i.e., dy, by a new nonnegative variable denoted by η. The constraints of the master problem are the first m 1 ones, i.e., those of the original problem for which the y-variables

	are absent:
	MP :

decomposition scheme Chapter 2 A Survivable variant of the Ring Star Problem

			Start
		Solve master (MP, η)
	Add a feasibility cut	Solve subproblem SP( x)	Add an optimality cut
	no		Subproblem feasible?
	problem. In the classical Benders decomposition approach, one Master Problem
	(a Mixed Integer Linear Program) is solved to optimality at each iteration. At each iteration, a new branch-and-bound tree is built from scratch and a lot of time is yes
	likely spent revisiting candidate solutions that have been eliminated earlier in the
	search. We can instead build a single search tree and generate valid cuts for the integer (and fractional) solutions encountered inside the tree, attaining the same η =SP( x)? no
	optimal solution, this is what we call the Branch-and-Benders-cut scheme that will
	be used during this thesis.	yes
			Stop
	Figure 1.3: Classical Benders

v 2 } do 7 starcost ← s v1 8 if s vv 1 < starcost then 9 starcost ← s vv 1 10 if s vv 2 < starcost then 11 starcost ← s vv 2 12 currentobjval ← currentobjval + starcost 13 if currentobjval < bestobjval then 14 bestobjval ← currentobjval

	15	bestsol ← {1, v 1 , v 2 }
	16 return bestsol, bestobjval
	if it is a terminal. Finally, for all

  The argument and the conclusion are the same if constraint (2.14) is not tight for m i . This means that constraint (2.14) has to be tight for both m i and m ′ i . The corresponding two equalities yield y ij = 0 for all j ∈ V \ {i, m i , m ′ i }, which again contradicts y iq > 0. The second subcase occurs when s im i < s im ′ i . Now, constraint (2.14) does not apply to m ′ i as m ′ i /∈ Ω i , so we can transform the optimal solution to LP + i by increasing y im ′ i by y iq and by setting y iq to zero. The resulting solution is feasible and its objective value has decreased by (s iqs im ′ i )y iq > 0, which again contradicts the fact that the initially considered solution was optimal. ■ Any optimal solution to LP i can be transformed into another optimal solution such that y im ⋆ i is the only nonzero y ij variable for all j in V \ ( V ∪ {i}) and y im i = y im ′ i are the only nonzero variables for all j in V \ {i}.

	Corollary 1.1.

and by decreasing y iq by ε. In the process, the objective value of the new feasible solution has been decreased by ε(s iq -

s im ′ i ) > 0,

which is a contradiction. Proof By Lemma 1, the only values of j ∈ V \ ( V ∪ {i}) such that y ij can be nonzero in an optimal solution to LP + i are those for which s ij = s im ⋆ i . If there are more that one such y ij variables, we can transform any optimal solution by updating y im ⋆ i to ∑ j∈V\( V∪{i})

  • We now consider the subcase in which s im i < s im ′ i . This implies that constraint(2.14) applies to m i only, so any optimal solution to LP + i can be transformed by updating y im ′ This yields a feasible solution whose objective value is the same as the one of the original optimal solution. As a result, constraint(2.14), which only applies to m i , is tight. It implies that y im i = y im ′ i and these two are the only nonzero variables for all j in V \ {i}. ■ Proof By corollary 1.1, any optimal solution to LP + i can be transformed into an optimal solution having at most three nonzero decision variables, namely y im ⋆ i , y im i and y im ′ i . It has also been shown that y im i = y im ′ i . Hence, by dropping all the zero decision variables, constraint (2.10) reduces to y im ⋆ i + y im i = 1, which means that variable y im i can be eliminated. By definition of m ⋆

	i to	∑
		j∈ V\{i,m i }
	Corollary 1.2. Any optimal solution to LP + i can be transformed into an integral optimal
	solution.

y ij and by setting y ij to zero for all

j ∈ V \ {i, m i , m ′ i }. i , constraint (2.12) is y im ⋆ i ≤ 1, so LP +

i is a single continuous variable linear program which is to minimize

  element row vector full of ones and block B 2,2 is a one-by-one matrix that contains zero. It will be shown that M ′ is non-singular by expressing its determinant, as det(A) × det(B) = det(B). It is first shown that B is non-singular: Since B 1,1 is the identity matrix of order |(H \ {m i }) ∩ V|, the rank of B is at least |(H \ {m i }) ∩ V|. Now, if the last column of B could be written as a linear combination of the first |(H \ {m i }) ∩ V| columns of B, we could express this column as

Table 2 .

 2 2 presents an analysis of the impact of V based on Class II instances 30.1 and 60.1 where V takes 5 different sizes. All instances are solved with ILP.In particular when V = ∅, the problem reduces to RSP. The columns of this table are as follows: CPU is the CPU time in seconds to solve the ILP model. "TL" is indicated when the time limit of one hour is reached; Gap represents the relative optimality gap of ILP. Its formula is (2.1) and (2.3)-(2.7) in the ILP model. It can be seen in this table that the problem difficulty increases drastically with the size of V, so it is clear that 1-S-RSP is much harder than the Ring Star Problem. Moreover, the number of uncertain

	nodes has a significant impact on the total number of constraints, since (2.5) has a
	cubic number of inequalities. We consider the most challenging setting, as a con-
	sequence, V is set to V \ {1} for both Class I and Class II instances, meaning the
	depot is certain and all other nodes are uncertain.
	Tables 2.3 and 2.4 present the results for Class I and Class II instances, respec-
	tively. The columns of these tables are as follows: CPU

UB -LB UB

where LB and UB are the ILP objective bound and incumbent objective value, both LB and UB are also displayed in Table 2.2. Column n_constraints shows the number of rows resulting from con-straints

BF is the CPU time spent by brute-force Algorithms 1 and 2, it is the same for the ILP and the Branch-and- Benders-cut models

. The brute-force algorithms are launched prior to the ILP and the Branch-and-Benders-cut models. CPU is the total CPU time in seconds, it includes the CPU time of column CPU BF. "TL" is indicated when the time limit of one hour is reached; Gap represents the relative optimality gap of both methods.

Its formula is the same as in Table

2

.2. Both LB and UB are also displayed in Tables 2.3 and 2.4; |H| is the number of hubs in the best solution found. When |H| = 4, the best solution is the one returned by Algorithm 2. Note that since there is a single certain node in the considered instances, Algorithm 1 cannot find any ring with three hubs. n_subtour is the number of subtour elimination constraints, i.e., feasibility cuts for Benders, and lazy constraints for ILP. Columns Nodes show the total number of explored nodes in the solver's branch-and-bound tree during the search. CPU

SP is the CPU time in seconds for solving the Benders subproblems. To obtain the running time of the master problem, we should subtract CPU BF and CPU SP to CPU. n_cut gives the number of optimality cuts in the Benders decomposition,

Table 2 .

 2 2: Impact of V's cardinality

	Instance n.ID		ILP
	n = |V|	V	CPU	Gap	LB	UB n_constraints
		∅ (Ring Star Problem)	5.59	0%	6,912	6,912	871
		{2, . . . , 8}	5.44	0%	7,545	7,545	3,713
	ClassII -30.1	{2, . . . , 15}	5.86	0%	8,335	8,335	6,555
		{2, . . . , 23}	5.10	0%	8,800	8,800	9,803
		{2, . . . , 30} = V \ {1}	TL	5.0% 13,535 14,247	12,645
		∅ (Ring Star Problem)	5.92	0%	9,906	9,906	3,541
		{2, . . . , 15}	6.24	0%	9,920	9,920	27,495
	ClassII -60.1	{2, . . . , 30}	7.63	0% 10,862 10,862	53,160
		{2, . . . , 45} 22.76	0% 13,980 13,980	78,825
		{2, . . . , 60} = V \ {1}	TL 19.8% 18,626 23,229	104,490
	Concluding remarks on the present chapter are given in Chapter 4.

Table 2 .

 2 4: Randomly generated instances Class II

	Instance n.ID		ILP							Branch-and-Benders-cut
	n = |V| CPU BF	CPU	Gap	LB	UB	|H| n_subtour	Nodes	CPU	CPU SP	Gap	LB	UB	|H| n_subtour	n_cut	Nodes
	ClassII -20.1	0.00	9.11	0.0% 10,200	10,200	4	3	3,578 156.11	0.77	0.0% 10,200	10,200	367	2028	318,762
	ClassII -20.2	0.00	6.57	0.0%	9,748	9,748	4	4	2,456	19.17	0.27	0.0%	9,748	9,748	51	613	39,770
	ClassII -20.3	0.00	5.53	0.0% 10,626 10,626	4	0	362	12.05	0.16	0.0% 10,626 10,626	32	303	17,521
	ClassII -20.4	0.00	5.49	0.0%	8,973	8,973	4	0	59	8.60	0.06	0.0%	8,973	8,973	14	201	6,538
	ClassII -20.5	0.00	6.70	0.0% 10,636 10,636	4	1	2,913	26.49	0.34	0.0% 10,636 10,636	45	801	52,752
	ClassII -30.1	0.03	TL	5.0% 13,535 14,247	12	122 336,852	TL	11.31 23.1% 10,818	14,071	6,644	11,149 690,368
	ClassII -30.2	0.03	TL	7.3% 15,216 16,422	11	211 432,828	TL	9.85 20.1% 12,579 15,760	7,268 11,419 725,196
	ClassII -30.3	0.03	14.09	0.0% 13,562 13,562	4	0	4,318	59.39	1.21	0.0% 13,562 13,562	71	1,065	92,113
	ClassII -30.4	0.01 707.83	0.0% 14,226 14,226	4	21	59,512	TL	13.47 14.3% 12,178 14,226	3,841 14,313 723,707
	ClassII -30.5	0.03	TL	1.1% 16,665 16,866	4	29 348,546	TL	14.37 19.8% 13,520 16,866	6,355 13,213 834,502
	ClassII -40.1	0.09	TL 12.8% 16,387 18,807	14	182	87,176	TL	18.64 25.0% 13,519	18,044	9,694	9,055 720,714
	ClassII -40.2	0.09	TL 12.4% 16,993 19,418	4	147	71,162	TL	19.15	27.0% 13,773 18,868	9,729	9,800 702,605
	ClassII -40.3	0.09	TL 15.0% 17,562 20,663	18	126	82,723	TL	17.33 31.2% 14,198 20,663	10,936	8,364 696,748
	ClassII -40.4	0.09	TL	7.7% 16,457 17,848	4	60	61,405	TL	24.08 18.5% 14,542 17,848	6,583 10,719 819,114
	ClassII -40.5	0.08	TL 10.4% 16,431 18,349	15	95	74,015	TL	21.99 28.0% 13,091 18,205	9,276	9,860 690,326
	ClassII -60.1	0.57	TL 19.8% 18,626 23,229	18	124	21,647	TL	38.19 32.1% 15,124 22,298	11,797	6,210 776,880
	ClassII -60.2	0.53	TL 13.0% 18,743 21,553	17	103	18,928	TL	48.81 24.0% 15,982	21,040	10,695	7,092 781,985
	ClassII -60.3	0.53	TL 14.7% 20,732 24,328	4	120	28,213	TL	45.62	23.5% 17,666 23,108	10,362	6,562 686,436
	ClassII -60.4	0.53	TL 21.3% 22,348 28,409	20	142	44,166	TL	44.80 29.6% 17,850 25,359	12,673	6,542 772,988
	ClassII -60.5	0.54	TL 20.1% 20,912 26,191	19	71	32,436	TL	31.23 29.6% 17,026 24,199	11,048	5,451 658,263
	ClassII -100.1	5.98	TL 16.7% 26,563 31,902	32	79	2,088	TL	73.76 31.3% 21,356 31,102	10,526	2,888 557,919
	ClassII -100.2	6.01	TL 37.1% 23,846 37,918	4	41	1,753	TL	61.85	40.7% 18,062 30,485	11,056	2,605 583,691
	ClassII -100.3	5.96	TL 34.9% 25,881 39,776	4	71	1,958	TL	87.13 28.7% 21,331 29,952	10,788	3,572 700,113
	ClassII -100.4	5.96	TL 28.4% 25,253 35,284	38	70	1,875	TL	56.41 34.6% 19,660 30,091	10,758	2,414 560,264
	ClassII -100.5	5.89	TL 15.1% 26,871 31,685	29	82	1,768	TL	52.31 36.7% 20,505	32,427	9,887	2,205 478,566
	ClassII -125.1	16.40	TL 37.2% 30,752 49,028	33	99	1,363	TL	86.19 33.8% 24,318 36,737	11,462	1,919 584,555
	ClassII -125.2	16.28	TL 19.1% 30,306 37,483	36	51	1,502	TL	78.09 31.7% 24,575 36,014	10,112	1,825 521,375
	ClassII -125.3	16.08	TL 35.1% 29,856 46,008	4	50	1,491	TL	63.30 35.1% 23,735	36,599	9,573	1,454 468,394
	ClassII -125.4	15.84	TL 36.3% 28,817 45,257	4	64	1,727	TL	76.93 39.8% 21,122	35,128	11,189	1,673 554,088
	ClassII -125.5	16.30	TL 47.1% 29,860 56,531	4	70	1,553	TL	79.23	34.0% 23,485 35,594	11,085	1,783 571,615
	ClassII -150.1	39.01 OUT OF MEMORY						TL	79.30 34.3% 26,027 39,664	8,443	1,036 441,501
	ClassII -150.2	39.19 OUT OF MEMORY						TL	95.37 34.4% 26,594 40,563	9,625	1,240 472,963
	ClassII -150.3	39.67 OUT OF MEMORY						TL	94.80 35.7% 25,283 39,330	9,983	1,246 514,406
	ClassII -150.4	40.03 OUT OF MEMORY						TL	98.45 38.3% 25,687 41,682	10,111	1,325 550,316
	ClassII -150.5	40.03 OUT OF MEMORY						TL	95.33 35.6% 27,252 42,339	9,563	1,315 485,729
	ClassII -200.1	173.61 OUT OF MEMORY						TL	110.18 38.7% 30,212 49,353	8,407	714 428,736
	ClassII -200.2	174.60 OUT OF MEMORY						TL	108.87 37.1% 29,995 47,761	8,276	642 395,399
	ClassII -200.3	173.61 OUT OF MEMORY						TL	113.77 40.4% 29,816 50,077	8,263	729 444,891
	ClassII -200.4	180.11 OUT OF MEMORY						TL	107.59 40.0% 29,572 49,344	8,822	696 446,267
	ClassII -200.5	173.63 OUT OF MEMORY						TL	111.37 40.2% 29,482 49,379	7,345	668 389,473

Table 2 . 5 :

 25 Variation of the results when 2-opt backup is not used

	Instance n-α	ILP				Branch-and-Benders-cut
	n = |V|	CPU	Gap	LB	UB	CPU	Gap	LB	UB
	eil 51-3	TL +14.05%	-1.02%	+7.80%	TL +187.92%	-0.60% +144.78%
	eil 51-5	TL +15.43%	-2.43%	+5.36%	TL	+42.91%	-0.36%	+20.76%
	eil 51-7	TL	0.00%	0.00%	0.00%	TL	0.00%	0.00%	0.00%
	pr 124-3	TL	0.00%	0.00%	0.00%	TL +113.92%	+2.41% +647.11%
	pr 124-5	TL	0.00%	0.00%	0.00%	TL	+51.13%	-1.59% +213.46%
	pr 124-7	TL	0.00%	0.00%	0.00%	TL	+17.09%	-1.53%	+72.19%
	ClassII -20.1	-1.54%	0.00%	0.00%	0.00% +20.86%	0.00%	0.00%	0.00%
	ClassII -30.1	TL	+38.00%	+0.97%	+3.05%	TL	+17.75%	+1.46%	+7.16%
	ClassII -40.1	TL	+35.16%	-1.32%	+4.07%	TL	+42.00%	+0.45%	+16.81%
	ClassII -60.1	TL	-1.52%	+0.27%	-0.09%	TL	+41.43%	-1.37%	+22.54%
	ClassII -100.1	TL +22.16%	+0.26%	+5.00%	TL	+40.89%	+1.09%	+24.28%
	ClassII -125.1 OUT OF MEMORY			TL	+22.49%	+0.16%	+13.33%

Table 3 .

 3

								1: TSPLIB instances
	Instance n-α			ILP						Branch-and-Benders-cut
	n = |V|	F	CPU	Gap	LB	UB	|H| n_subtour Nodes	CPU CPU SP	Gap	LB	UB	|H| n_subtour n_cut	Nodes
	eil51-3	0 (no failures)	40.41	0%	1311.00	1311.00	51	13	1	7.79	0.00	0%	1311.00	1311.00	51	16	0
	eil51-3	7 (one week)	42.67	0%	1315.76	1315.76	51	16	1	9.32	0.16	0%	1315.76	1315.76	51	29	5
	eil51-3	31 (one month)	41.31	0%	1332.08	1332.08	51	11	1	9.59	0.27	0%	1332.08	1332.08	51	32	14
	eil51-3 183 (six months)	102.10	0%	1435.44	1435.44	51	56	397	50.90	2.29	0%	1435.44	1435.44	51	1457	232
	eil51-5	0 (no failures)	17.50	0%	2042.00	2042.00	37	1	1	10.42	0.00	0%	2042.00	2042.00	37	335	0
	eil51-5	7 (one week)	22.42	0%	2052.08	2052.08	37	3	1	11.61	0.17	0%	2052.08	2052.08	37	483	7
	eil51-5	31 (one month)	45.88	0%	2086.64	2086.64	37	17	1	19.76	0.32	0%	2086.64	2086.64	37	1311	22
	eil51-5 183 (six months)	996.89	0%	2290.41	2290.41	40	791	5455	TL	5.00	5.8%	2157.00	2290.41	40	14263	479
	eil51-7	0 (no failures)	284.10	0%	2147.00	2147.00	16	173	259	14.88	0.00	0%	2147.00	2147.00	17	234	0
	eil51-7	7 (one week)	301.48	0%	2168.51	2168.51	16	211	492	34.95	0.53	0%	2168.51	2168.51	17	1184	37
	eil51-7	31 (one month) 2017.40	0%	2232.86	2232.86	20	1483	6945	912.89	5.29	0%	2232.86	2232.86	19	2006	520
	eil51-7 183 (six months)	TL 11.0%	2246.73	2524.89	23	2000	4134	TL	50.10	12.9%	2200.52	2526.72	24	2815	5665
	berlin52-3	0 (no failures)	14.90	0%	22657.00	22657.00	52	2	0	7.42	0.00	0%	22657.00	22657.00	52	14	0
	berlin52-3	7 (one week)	19.79	0%	22805.33	22805.33	52	3	1	8.80	0.13	0%	22805.33	22805.33	52	11	3
	berlin52-3	31 (one month)	22.44	0%	23313.89	23313.89	52	5	1	9.07	0.16	0%	23313.89	23313.89	52	15	8
	berlin52-3 183 (six months)	152.98	0%	26534.77	26534.77	52	79	359	41.40	3.12	0%	26534.77	26534.77	52	1252	328
	berlin52-5	0 (no failures)	106.62	0%	36147.00	36147.00	41	92	1	TL	0.00	8.7%	33904.00	37141.00	35	20498	0
	berlin52-5	7 (one week)	136.64	0%	36471.68	36471.68	42	98	1	TL	0.21	9.2%	34058.00	37493.25	40	20367	14
	berlin52-5	31 (one month)	83.80	0%	37365.44	37365.44	42	61	43	TL	0.52	27.2%	33656.00	46214.32	43	17637	46
	berlin52-5 183 (six months)	2532.18	0%	42915.82	42915.82	43	611	8077	TL	0.29 NO SOLUTION FOUND	34033.00			16712	17
	berlin52-7	0 (no failures)	180.30	0%	37413.00	37413.00	24	100	1	32.54	0.00	0%	37413.00	37413.00	24	2411	0
	berlin52-7	7 (one week)	189.71	0%	37840.19	37840.19	24	109	51	13.74	0.23	0%	37840.19	37840.19	24	163	9
	berlin52-7	31 (one month)	286.66	0%	39116.27	39116.27	24	158	354	63.03	1.02	0%	39116.27	39116.27	24	948	99
	berlin52-7 183 (six months)	TL 10.1%	41679.79	46362.58	26	1661	4189	TL	37.73	5.7%	39741.62	42122.89	28	2893	4148
	brazil58-3	0 (no failures)	73.31	0%	76185.00	76185.00	58	22	1	8.08	0.00	0%	76185.00	76185.00	58	35	0
	brazil58-3	7 (one week)	83.91	0%	76856.25	76859.82	58	29	11	10.64	0.51	0%	76859.82	76859.82	58	32	30
	brazil58-3	31 (one month)	115.47	0%	79122.06	79122.06	58	60	438	37.66	4.33	0%	79122.06	79122.06	58	385	349
	brazil58-3 183 (six months)	1769.39	0%	93449.58	93449.58	58	345	4663	TL	37.43	4.4%	89354.40	93449.56	58	2780	3146
	brazil58-5	0 (no failures)	244.64	0% 115045.00 115045.00	40	113	1	TL	0.00	42.2% 103755.00 179530.00	44	16626	0
	brazil58-5	7 (one week)	140.88	0%	116802.25 116802.25	41	55	1	TL	0.17 NO SOLUTION FOUND 103736.67			19186	2
	brazil58-5	31 (one month)	158.42	0% 121404.25 121404.25	41	53	43	TL	0.17 NO SOLUTION FOUND 103731.25			19058	2
	brazil58-5 183 (six months)	TL	1.3% 144714.39 146551.75	43	767	7705	TL	0.16 NO SOLUTION FOUND 103725.71			18830	2
	brazil58-7	0 (no failures)	247.84	0% 126807.00 126807.00	28	78	1	TL	0.00	45.1% 110746.00 201549.00	35	17638	0
	brazil58-7	7 (one week)	311.28	0%	129743.78 129743.78	28	114	13	22.28	0.55	0% 129743.78 129743.78	28	1355	23
	brazil58-7	31 (one month)	1832.18	0% 138217.58 138217.58	29	371	4055	TL	1.55	5.2% 131753.92 138968.04	27	15676	120
	brazil58-7 183 (six months)	TL 14.8% 139208.49 163387.80	27	892	1971	TL	2.72	26.0% 131682.10 177913.63	25	17139	153
	st70-3	0 (no failures)	218.86	0%	2059.00	2059.00	70	24	1	10.05	0.00	0%	2059.00	2059.00	70	87	0
	st70-3	7 (one week)	189.08	0%	2065.79	2065.79	70	19	1	17.19	0.25	0%	2065.79	2065.79	70	665	9
	st70-3	31 (one month)	183.24	0%	2089.07	2089.07	70	25	1	20.96	0.45	0%	2089.07	2089.07	70	936	17
	st70-3 183 (six months)	446.91	0%	2223.21	2223.21	70	93	616	170.86	11.94	0%	2223.21	2223.21	70	2080	499
	st70-5	0 (no failures)	424.43	0%	3164.00	3164.00	56	85	1	279.73	0.00	0%	3164.00	3164.00	54	5879	0
	st70-5	7 (one week)	278.03	0%	3177.16	3177.23	56	80	75	50.05	0.30	0%	3177.23	3177.23	55	1583	9
	st70-5	31 (one month)	473.24	0%	3222.59	3222.59	55	81	24	54.60	0.62	0%	3222.59	3222.59	56	1895	19
	st70-5 183 (six months)	TL	1.8%	3430.53	3492.42	57	758	3598	TL	2.49	14.7%	3174.00	3719.04	56	12110	110
	st70-7	0 (no failures)	860.21	0%	3449.00	3449.00	31	125	1	16.70	0.00	0%	3449.00	3449.00	31	157	0
	st70-7	7 (one week)	768.83	0%	3472.49	3472.49	31	137	109	29.26	0.73	0%	3472.45	3472.49	31	251	34
	st70-7	31 (one month) 1180.62	0%	3543.73	3543.73	33	458	1551	179.73	3.28	0%	3543.73	3543.73	33	2000	158
	st70-7 183 (six months)	TL	9.4%	3558.85	3928.54	34	700	1073	TL	74.84	10.2%	3526.29	3928.54	33	3296	3836
	eil76-3	0 (no failures)	142.99	0%	1666.00	1666.00	76	10	1	8.03	0.00	0%	1666.00	1666.00	76	13	0
	eil76-3	7 (one week)	159.02	0%	1672.37	1672.37	76	12	1	9.78	0.30	0%	1672.37	1672.37	76	22	4
	eil76-3	31 (one month)	211.92	0%	1690.84	1690.84	76	22	1	11.48	0.64	0%	1690.84	1690.84	76	57	14
	eil76-3 183 (six months)	753.11	0%	1782.97	1782.97	76	137	822	121.82	9.16	0%	1782.97	1782.97	76	1697	248
	eil76-5	0 (no failures)	467.66	0%	2533.00	2533.00	57	28	1	9.40	0.00	0%	2533.00	2533.00	57	69	0
	eil76-5	7 (one week)	166.37	0%	2542.52	2542.52	57	34	31 OUT OF MEMORY
	eil76-5	31 (one month)	589.25	0%	2575.16	2575.16	57	38	1 OUT OF MEMORY
	eil76-5 183 (six months)	OUT OF MEMORY						TL	6.03	5.5%	2633.90	2787.22	58	11168	160
	eil76-7	0 (no failures) 2456.89	0%	2572.00	2572.00	31	180	64	104.07	0.00	0%	2572.00	2572.00	31	1333	0
	eil76-7	7 (one week)	1096.08	0%	2586.70	2586.70	31	197	187	40.87	0.56	0%	2586.70	2586.70	31	232	12
	eil76-7	31 (one month)	TL	0.6%	2621.65	2637.10	31	627	1167	243.32	4.09	0%	2637.10	2637.10	31	2005	113
	eil76-7 183 (six months) OUT OF MEMORY						TL	105.35	9.4%	2636.20	2909.10	30	2383	3009
	pr76-3	0 (no failures) OUT OF MEMORY						34.08	0.00	0% 324510.00 324510.00	76	525	0
	pr76-3	7 (one week)	493.67	0%	325972.72 325972.72	76	176	1716	33.76	0.39	0% 325972.72 325972.72	76	616	6
	pr76-3	31 (one month)	435.28	0% 330987.76 330987.76	76	132	1266	157.83	1.44	0% 330987.76 330987.76	76	2000	29
	pr76-3 183 (six months)	OUT OF MEMORY						TL	48.56	1.1% 358901.03 362749.66	76	2998	1327
	pr76-5	0 (no failures) 2029.15	0% 500431.00 500431.00	61	172	7 3240.21	0.00	0% 500428.50 500431.00	61	12118	0
	pr76-5	7 (one week) OUT OF MEMORY						TL	0.64	21.4% 486662.33 619456.84	66	12282	13
	pr76-5	31 (one month)	960.01	0% 510667.05 510667.05	61	360	717	TL	1.04	23.7% 486734.83 637978.88	61	12300	25
	pr76-5 183 (six months)	OUT OF MEMORY						TL	0.37 NO SOLUTION FOUND 486431.64			10407	6
	pr76-7	0 (no failures) OUT OF MEMORY						158.88	0.00	0% 555888.00 555888.00	39	1754	0
	pr76-7	7 (one week) 2555.39	0%	560503.45 560503.45	39	1162	4291	243.31	1.69	0% 560503.45 560503.45	39	2000	32
	pr76-7	31 (one month)	TL	4.0%	556861.08 579846.96	44	612	1056	TL	8.02	1.2% 565851.01 572902.66	42	2065	212
	pr76-7 183 (six months)	OUT OF MEMORY						TL	47.38	12.3% 559427.44 637935.65	45	4587	1386
	gr96-3	7 (one week) OUT OF MEMORY						16.48	1.03	0%	1592.10	1592.10	96	122	9
	gr96-3	31 (one month) OUT OF MEMORY						50.02	3.62	0%	1619.72	1619.72	96	1203	41
	gr96-5	7 (one week) OUT OF MEMORY						76.75	1.48	0%	2442.65	2442.77	75	1433	11
	gr96-7	31 (one month) OUT OF MEMORY						TL	0.59 NO SOLUTION FOUND	2405.09			8579	4
	gr96-7 183 (six months) OUT OF MEMORY						TL	0.37 NO SOLUTION FOUND	2399.99			8625	2
	rat99-3	7 (one week) OUT OF MEMORY						12.75	0.85	0%	3710.84	3710.84	99	36	8
	rat99-3	31 (one month)	OUT OF MEMORY						16.08	1.66	0%	3737.72	3737.72	99	79	12
	rat99-5	7 (one week) OUT OF MEMORY						141.40	2.03	0%	5998.00	5998.58	89	2696	13
	rat99-5	31 (one month)	OUT OF MEMORY						1406.29	5.74	0%	6045.00	6045.14	89	10006	53
	rat99-7	7 (one week) OUT OF MEMORY						210.01	1.96	0%	6559.30	6559.30	41	478	19

Table 3 .

 3 1: TSPLIB instances (continued)

	Instance n-α		ILP		Branch-and-Benders-cut
	n = |V|	F	CPU Gap LB UB	|H| n_subtour Nodes	CPU CPU SP	Gap	LB	UB	|H| n_subtour n_cut	Nodes
	kroA100-3	7 (one week)	OUT OF MEMORY		40.12	1.41	0%	64120.60	64120.60 100	1019	12
	kroA100-3	31 (one month) OUT OF MEMORY		72.49	2.98	0%	64698.55	64698.55 100	1376	28
	kroA100-5	7 (one week) OUT OF MEMORY		TL	0.54 NO SOLUTION FOUND	98483.50			8917	4
	kroA100-5	31 (one month) OUT OF MEMORY		TL	0.55	NO SOLUTION FOUND	98482.00			8947	4
	kroA100-5 183 (six months) OUT OF MEMORY		TL	0.34 NO SOLUTION FOUND	98520.50			9110	2
	kroA100-7	7 (one week) OUT OF MEMORY		TL	0.33 NO SOLUTION FOUND	98676.11			7820	2
	kroA100-7	31 (one month) OUT OF MEMORY		TL	0.33	NO SOLUTION FOUND	98588.38			7889	2
	kroA100-7 183 (six months) OUT OF MEMORY		TL	0.32 NO SOLUTION FOUND	98676.58			7802	2
	kroB100-3	7 (one week) OUT OF MEMORY		36.16	1.27	0%	66634.35	66634.35 100	530	10
	kroB100-3	31 (one month) OUT OF MEMORY		52.19	2.95	0%	67168.76	67168.76 100	757	26
	kroB100-5	31 (one month) OUT OF MEMORY		TL	1.17 NO SOLUTION FOUND 104452.00			9078	11
	kroB100-5 183 (six months) OUT OF MEMORY		TL	1.25 NO SOLUTION FOUND 104399.90			9436	12
	kroB100-7	7 (one week) OUT OF MEMORY		146.54	2.24	0% 118718.67 118718.67	47	1528	20
	kroC100-3	7 (one week) OUT OF MEMORY		22.69	1.06	0%	62465.97	62465.97 100	163	6
	kroC100-7	7 (one week) OUT OF MEMORY		TL	0.34 NO SOLUTION FOUND	95471.74			8096	2
	kroC100-7	31 (one month) OUT OF MEMORY		TL	0.33	NO SOLUTION FOUND	95440.01			7783	2
	kroC100-7 183 (six months) OUT OF MEMORY		TL	0.34 NO SOLUTION FOUND	95440.01			7783	2
	kroD100-3	7 (one week) OUT OF MEMORY		18.37	1.17	0%	64128.11	64128.11 100	119	9
	kroD100-3	31 (one month) OUT OF MEMORY		25.85	2.62	0%	64713.60	64713.60 100	148	23
	kroD100-5	7 (one week) OUT OF MEMORY		TL	0.33 NO SOLUTION FOUND	95806.38			8434	2
	kroD100-5	31 (one month) OUT OF MEMORY		TL	0.38	NO SOLUTION FOUND	95791.67			8065	2
	kroD100-5 183 (six months) OUT OF MEMORY		TL	0.34 NO SOLUTION FOUND	95794.00			8185	2
	kroD100-7	7 (one week) OUT OF MEMORY		182.22	4.22	0% 117571.65 117571.65	48	1513	43
	kroD100-7	31 (one month) OUT OF MEMORY		2164.30	32.31	0% 119490.21 119490.21	53	2013	301
	kroE100-3	7 (one week) OUT OF MEMORY		53.12	1.34	0%	66437.39	66437.39 100	1264	11
	kroE100-3	31 (one month) OUT OF MEMORY		77.78	2.80	0%	67055.87	67055.87 100	1340	29
	kroE100-5 183 (six months) OUT OF MEMORY		TL	0.33	NO SOLUTION FOUND 102621.00			9126	2
	kroE100-7	7 (one week) OUT OF MEMORY		94.10	2.00	0% 117103.25 117103.25	51	1708	18
	kroE100-7	31 (one month) OUT OF MEMORY		200.64	5.64	0% 119113.25 119113.25	51	1970	58
	rd100-3	7 (one week) OUT OF MEMORY		17.04	0.97	0%	23851.97	23851.97 100	127	8
	rd100-3	31 (one month)	OUT OF MEMORY		23.52	1.47	0%	24083.12	24083.12 100	243	11
	rd100-5	7 (one week) OUT OF MEMORY		TL	0.38 NO SOLUTION FOUND	35610.00			7945	2
	rd100-5	31 (one month)	OUT OF MEMORY		TL	0.33 NO SOLUTION FOUND	35597.00			7826	2
	rd100-5 183 (six months)	OUT OF MEMORY		TL	0.41	NO SOLUTION FOUND	35599.00			7962	2
	rd100-7	7 (one week) OUT OF MEMORY		168.53	2.59	0%	41213.96	41213.96	46	1521	24
	rd100-7	31 (one month)	OUT OF MEMORY		863.01	18.82	0%	41832.19	41832.19	47	2040	183
	eil101-3	7 (one week) OUT OF MEMORY		13.25	0.49	0%	1968.55	1968.55 101	56	4
	eil101-3	31 (one month) OUT OF MEMORY		18.18	1.44	0%	1984.15	1984.15 101	95	11
	eil101-3 183 (six months) OUT OF MEMORY		432.02	20.39	0%	2082.95	2082.95 101	1709	169
	eil101-5	7 (one week) OUT OF MEMORY		28.27	1.06	0%	3039.23	3039.23	78	653	9
	lin105-3 183 (six months) OUT OF MEMORY		271.74	37.64	0%	46943.99	46943.99 105	2150	360
	lin105-5	7 (one week) OUT OF MEMORY		TL	0.36 NO SOLUTION FOUND	65083.67			8670	2
	lin105-5	31 (one month)	OUT OF MEMORY		TL	0.35	NO SOLUTION FOUND	65065.86			7928	2
	lin105-5 183 (six months)	OUT OF MEMORY		TL	0.35	NO SOLUTION FOUND	65077.50			8385	2
	lin105-7	7 (one week) OUT OF MEMORY		TL	0.38 NO SOLUTION FOUND	73087.75			10716	2
	lin105-7	31 (one month)	OUT OF MEMORY		TL	0.36	NO SOLUTION FOUND	73073.70			10233	2
	pr107-5 183 (six months) OUT OF MEMORY		TL	0.40	NO SOLUTION FOUND 143454.00			12456	2
	pr107-7	7 (one week) OUT OF MEMORY		TL	0.50 NO SOLUTION FOUND 224795.14			8004	3
	pr107-7	31 (one month)	OUT OF MEMORY		TL	0.69 NO SOLUTION FOUND 224749.38			7611	3
	pr107-7 183 (six months)	OUT OF MEMORY		TL	0.50	NO SOLUTION FOUND 224766.64			7696	3
	gr120-5	7 (one week) OUT OF MEMORY		TL	0.34 NO SOLUTION FOUND	7350.78			6693	1
	gr120-5	31 (one month)	OUT OF MEMORY		TL	0.33 NO SOLUTION FOUND	7349.00			6305	1
	gr120-5 183 (six months)	OUT OF MEMORY		TL	0.34	NO SOLUTION FOUND	7346.33			6202	1
	gr120-7	7 (one week) OUT OF MEMORY		TL	0.57 NO SOLUTION FOUND	7452.32			5051	2
	gr120-7	31 (one month)	OUT OF MEMORY		TL	0.63 NO SOLUTION FOUND	7452.59			4469	2
	gr120-7 183 (six months)	OUT OF MEMORY		TL	0.57	NO SOLUTION FOUND	7458.37			4725	2
	pr124-5	7 (one week) OUT OF MEMORY		TL	0.58 NO SOLUTION FOUND 271613.50			7142	2
	pr124-5	31 (one month)	OUT OF MEMORY		TL	0.58 NO SOLUTION FOUND 271573.62			6817	2
	pr124-5 183 (six months)	OUT OF MEMORY		TL	0.57	NO SOLUTION FOUND 271569.50			6684	2
	bier127-5	7 (one week) OUT OF MEMORY		TL	0.69 NO SOLUTION FOUND 527657.56			7718	2
	bier127-5 183 (six months) OUT OF MEMORY		TL	0.68 NO SOLUTION FOUND 527657.56			7720	2
	ch130-7	7 (one week) OUT OF MEMORY		TL	0.95 NO SOLUTION FOUND	26315.37			6475	2
	ch130-7	31 (one month)	OUT OF MEMORY		TL	0.98 NO SOLUTION FOUND	26301.28			5981	2
	ch130-7 183 (six months)	OUT OF MEMORY		TL	0.91	NO SOLUTION FOUND	26308.19			6212	2
	pr136-5	7 (one week) OUT OF MEMORY		TL	0.69 NO SOLUTION FOUND 449036.00			8565	2
	pr136-5	31 (one month)	OUT OF MEMORY		TL	0.96	NO SOLUTION FOUND 449023.17			8499	2
	pr136-5 183 (six months)	OUT OF MEMORY		TL	0.98	NO SOLUTION FOUND 449036.00			8563	2

Table 3 .

 3 1: TSPLIB instances (continued)

	Instance n-α		ILP	Branch-and-Benders-cut
	n = |V|	F	CPU Gap LB UB	|H| n_subtour Nodes CPU CPU SP	Gap	LB UB	|H| n_subtour n_cut Nodes
	gr137-3	7 (one week) OUT OF MEMORY	TL	0.70 NO SOLUTION FOUND	1109.44	5761	2
	gr137-3	31 (one month)	OUT OF MEMORY	TL	0.70 NO SOLUTION FOUND	1103.00	5916	2
	gr137-3 183 (six months) OUT OF MEMORY	TL	0.71 NO SOLUTION FOUND	1103.00	5968	2
	gr137-5	7 (one week) OUT OF MEMORY	TL	0.97 NO SOLUTION FOUND	1831.00	6147	3
	gr137-5	31 (one month)	OUT OF MEMORY	TL	0.98 NO SOLUTION FOUND	1830.50	5731	3
	gr137-5 183 (six months) OUT OF MEMORY	TL	0.97 NO SOLUTION FOUND	1789.00	6579	3
	gr137-7	7 (one week) OUT OF MEMORY	TL	0.99 NO SOLUTION FOUND	2256.88	6310	3
	gr137-7	31 (one month)	OUT OF MEMORY	TL	0.98 NO SOLUTION FOUND	2324.77	5648	3
	gr137-7 183 (six months) OUT OF MEMORY	TL	0.70 NO SOLUTION FOUND	2309.88	5871	2
	pr144-3	7 (one week) OUT OF MEMORY	TL	2.24 NO SOLUTION FOUND	142777.17	4076	4
	pr144-5	7 (one week) OUT OF MEMORY	TL	1.86 NO SOLUTION FOUND	229849.50	4249	3
	pr144-5	31 (one month)	OUT OF MEMORY	TL	1.78 NO SOLUTION FOUND	229849.50	4233	3
	pr144-5 183 (six months) OUT OF MEMORY	TL	1.72 NO SOLUTION FOUND	229834.50	4265	3
	ch150-5	7 (one week) OUT OF MEMORY	TL	1.14 NO SOLUTION FOUND	29902.00	6100	2
	ch150-5	31 (one month)	OUT OF MEMORY	TL	1.13 NO SOLUTION FOUND	29891.00	6057	2
	ch150-5 183 (six months) OUT OF MEMORY	TL	1.12 NO SOLUTION FOUND	29906.33	5886	2
	ch150-7	7 (one week) OUT OF MEMORY	TL	1.14 NO SOLUTION FOUND	30741.90	5004	2
	ch150-7	31 (one month)	OUT OF MEMORY	TL	1.14 NO SOLUTION FOUND	30749.51	5221	2
	ch150-7 183 (six months) OUT OF MEMORY	TL	1.13 NO SOLUTION FOUND	30729.73	4948	2
	kroA150-5	7 (one week) OUT OF MEMORY	TL	1.36 NO SOLUTION FOUND	116620.00	5403	2
	kroA150-5	31 (one month)	OUT OF MEMORY	TL	1.39 NO SOLUTION FOUND	116620.00	5390	2
	kroA150-5 183 (six months) OUT OF MEMORY	TL	1.39 NO SOLUTION FOUND	116620.00	5403	2
	kroB150-5	7 (one week) OUT OF MEMORY	TL	1.37 NO SOLUTION FOUND	115046.87	5125	2
	kroB150-5	31 (one month)	OUT OF MEMORY	TL	2.99 NO SOLUTION FOUND	115047.39	5152	5
	kroB150-5 183 (six months) OUT OF MEMORY	TL	2.92 NO SOLUTION FOUND	115049.37	5173	5
	kroB150-7	7 (one week) OUT OF MEMORY	TL	1.40 NO SOLUTION FOUND	116568.17	5733	2
	kroB150-7 183 (six months) OUT OF MEMORY	TL	1.40 NO SOLUTION FOUND	116478.55	5702	2
	pr152-3	7 (one week) OUT OF MEMORY	TL	1.38 NO SOLUTION FOUND	216172.00	4699	2
	pr152-3	31 (one month)	OUT OF MEMORY	TL	1.40 NO SOLUTION FOUND	216154.81	4661	2
	pr152-5	7 (one week) OUT OF MEMORY	TL	1.46 NO SOLUTION FOUND	259239.33	6034	2
	pr152-5	31 (one month)	OUT OF MEMORY	TL	1.53 NO SOLUTION FOUND	259161.17	5815	2
	pr152-5 183 (six months) OUT OF MEMORY	TL	1.45 NO SOLUTION FOUND	259239.33	6043	2
	pr152-7	31 (one month)	OUT OF MEMORY	TL	3.94 NO SOLUTION FOUND	448642.29	3726	6
	pr152-7 183 (six months) OUT OF MEMORY	TL	1.46 NO SOLUTION FOUND	447520.33	4375	2
	u159-5	7 (one week) OUT OF MEMORY	TL	2.25 NO SOLUTION FOUND	197366.14	5333	4
	u159-5	31 (one month) OUT OF MEMORY	TL	3.13 NO SOLUTION FOUND 197335.50	4916	4
	u159-5 183 (six months) OUT OF MEMORY	TL	1.17 NO SOLUTION FOUND	198057.58	5582	2
	d198-5	31 (one month) OUT OF MEMORY	TL	3.94 NO SOLUTION FOUND	69319.57	3965	3
	d198-5 183 (six months)	OUT OF MEMORY	TL	3.77 NO SOLUTION FOUND	69346.73	4252	3
	d198-7	7 (one week) OUT OF MEMORY	TL	2.79 NO SOLUTION FOUND	68892.88	4114	2
	d198-7	31 (one month) OUT OF MEMORY	TL	2.72 NO SOLUTION FOUND	68892.88	4117	2
	d198-7 183 (six months) OUT OF MEMORY	TL	2.81 NO SOLUTION FOUND	68892.88	4123	2
	kroA200-3	7 (one week) OUT OF MEMORY	TL	2.84 NO SOLUTION FOUND	83722.12	3323	2
	kroA200-3	31 (one month)	OUT OF MEMORY	TL	2.88 NO SOLUTION FOUND	83722.12	3350	2
	kroA200-3 183 (six months) OUT OF MEMORY	TL	2.83 NO SOLUTION FOUND	83722.12	3350	2
	kroA200-5	7 (one week) OUT OF MEMORY	TL	2.84 NO SOLUTION FOUND	127573.50	4522	2
	kroA200-5	31 (one month)	OUT OF MEMORY	TL	2.74 NO SOLUTION FOUND	127573.50	4525	2
	kroA200-5 183 (six months) OUT OF MEMORY	TL	2.84 NO SOLUTION FOUND	127573.50	4528	2
	kroA200-7	7 (one week) OUT OF MEMORY	TL	2.94 NO SOLUTION FOUND	130447.11	4836	2
	kroA200-7	31 (one month)	OUT OF MEMORY	TL	2.94 NO SOLUTION FOUND	130428.05	4592	2
	kroA200-7 183 (six months) OUT OF MEMORY	TL	3.00 NO SOLUTION FOUND	130287.12	4947	2
	kroB200-3	7 (one week) OUT OF MEMORY	TL	3.89 NO SOLUTION FOUND	87553.25	3180	3
	kroB200-3	31 (one month)	OUT OF MEMORY	TL	3.76 NO SOLUTION FOUND	87553.25	3202	3
	kroB200-3 183 (six months) OUT OF MEMORY	TL	3.89 NO SOLUTION FOUND	87553.25	3191	3
	kroB200-5	7 (one week) OUT OF MEMORY	TL	3.91 NO SOLUTION FOUND	127515.63	4212	3
	kroB200-5	31 (one month)	OUT OF MEMORY	TL	3.85 NO SOLUTION FOUND	127515.63	4213	3
	kroB200-5 183 (six months) OUT OF MEMORY	TL	3.99 NO SOLUTION FOUND	127515.63	4212	3
	kroB200-7	7 (one week) OUT OF MEMORY	TL	2.98 NO SOLUTION FOUND	130634.83	4205	2
	kroB200-7	31 (one month)	OUT OF MEMORY	TL	2.85 NO SOLUTION FOUND	130634.83	4204	2
	kroB200-7 183 (six months) OUT OF MEMORY	TL	2.88 NO SOLUTION FOUND	130598.21	3997	2

Table 3 . 2

 32

: Numerical experiments for comparing 1-R-RSP and 1-S-RSP Chapter 4

return bestsol, bestobjval

return (x ij ) ij∈E , (x ′ ij ) ij∈E , new_cost

Acknowledgements

Algorithm 6: CRITICALTRIPLET(n, V, V, V ′ , E ′ , c ′ , d ′ , x, y) returns B and the critical triplet (i ⋆ , j ⋆ , k ⋆ ) 1 Let adj be an array of |V ′ | empty lists; 2 foreach (i, j) ∈ E ′ do 3 if x ij = 1 then 4 adj [i].append(j); 5 adj [j].append(i); [1] > adj[i] [2] then [START_REF] Ben-Tal | Robust solutions of uncertain linear programs[END_REF] Exchange adj[i] [1] and adj[i] [2]; [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF] Let costReconnection be a |V|-element array;

while y ij = 0 do j ← j + 1; [2] ;

Algorithm 7: Computation of an optimal solution to the subproblem's dual

Proof: If there does not exist any optimal solution S ′ to 1-R-RSP(F) such that K S ′ + FB S ′ < K S F 0 + FB S F 0 for any F ≥ F 0 , the lemma obviously holds. Hence, we now assume that there exists F > F 0 such that an optimal solution S ′ to 1-R-RSP(F) satisfies K S ′ + FB S ′ < K S F 0 + FB S F 0 , this inequality is denoted by (A).

Note that S ′ cannot be optimal for 1-R-RSP(F 0 ) because no optimal solution S to 1-R-RSP(F 0 ) can satisfy (A), by Observation 1. Consequently we have

which can also be written as

the largest value for which S F 0 , a B-optimal solution to 1-R-RSP(F 0 ), is an optimal solution to 1-R-RSP(F 1 ). Since S F 0 is no longer an optimal solution to 1-R-RSP(F) for F > F 1 , it can be concluded by the previous lemma that it is not a B-optimal solution to 1-R-RSP(F 1 ). This means that any B-optimal solution to 1-R-RSP(F 1 ), denoted by S F 1 is such that B S F 1 < B S F 0 and

This shows that g(F), the function that associates the optimal objective function value of 1-R-RSP(F) as a function of F, is continuous, piecewise linear, and concave. Consequently, g(F) can be specified by an ordered sequence of q pairs (F 0 , S 0 ), (F 1 , S 1 ), . . . (F q-1 , S q-1 ), where F 0 = 0, and

and the corresponding value of K k can be visualized at the intersection of the line segment with the line F = 0. Figure 3.2 also shows the interval upon which S k is optimal.

g(F)

• Sort the stored pairs (F, S) by increasing order of F. If we find two consecutive pairs with the same value of F, delete the one with the largest B S value.

If two consecutive pairs have the same B value, the pair associated with the largest F value should be deleted.

The pseudocode of EXPLORE(F ℓ , S ℓ , F r , S r ) is given in Algorithm 8, and the dif- ferent situations that can occur in the course of the algorithm are illustrated by Algorithm 8: EXPLORE(F ℓ , S ℓ , F r , S r )

Prior to each call to EXPLORE(F ℓ , S ℓ , F r , S r ), solution S ℓ is optimal for 1-R-RSP(F ℓ ) and S r is optimal for 1-R-RSP(F r ). If B S ℓ = B S r , 3 ensures that solution S ℓ (or S r ) is an optimal solution to 1-R-RSP(F) for all F ∈ [F ℓ , F r ], this situation is pictured in Figure 3.3, left, where the red line and the blue one overlap. Otherwise, B S ℓ < B S r and we compute F m as the value of F for which the cost of solutions S ℓ and S r are equal, i.e., K Figure 3.3, center), then solution S r is an optimal solution to 1-R-RSP(F) for all F ∈ [F ℓ , F r ], and the pair (F ℓ , S r ) is stored. Symmetrically, if F m = F r (see Figure 3.3, right), then solution S ℓ is an optimal solution to 1-R-RSP(F) for all F ∈ [F ℓ , F r ]

Solving 1-R-RSP(F) for all F ≥ F ℓ

Let F ℓ be a given nonnegative constant, and suppose that we want to solve 1-R-RSP(F) for all F ≥ F ℓ . Note that such a problem may not be very relevant in practice, as we may assume that an upper bound for the total time during which a hub is down may not exceed the time horizon. We cannot apply the previous approach to address this problem, because [F ℓ , +∞) is not a closed interval. However, we may circumvent the issue by considering the solution S ∞ , defined as follows:

Where σ is the set of all the feasible solutions to 1-R-RSP(F) for some F ≥ 0. By the corollary, g(F) is continuous, linear piecewise and concave, so it follows that there exists F 0 ≥ 0 such that the objective value of solution S ∞ is less than or equal to the solution value to any feasible solution to 1-R-RSP(F), for all F ≥ F 0 . Solution S ∞ can be computed by solving the following two successive variants of 1-R-RSP, in which there is no F input parameter:

• Obtain B S ∞ by solving a variant of 1-R-RSP where the objective function is to minimize B

• Obtain K S ∞ by solving a second variant of 1-R-RSP where the objective is to

and by enforcing the constraint

It can be observed that if |V\ V| ≥ 3, then S ∞ is such that B S ∞ = 0. Indeed, any solution where the ring is made of certain hubs only is insensitive to failures.

In such a case, there is no need to address the first variant of 1-R-RSP, since we already know that B S ∞ is zero.

We can solve 1-R-RSP(F) for all F ≥ F ℓ as follows:

• Solve 1-R-RSP(F ℓ ), and obtain solution S ℓ (so K S ℓ and B S ℓ are known)

• Compute solution S ∞ as shown above

Comparing the cost of 1-S-RSP and 1-R-RSP(F)

Now, we can compare an optimal solution of problem 1-S-RSP with the optimal solutions of 1-R-RSP(F) for F in some interval using a graphical approach. It suffices to plot g(F) in the considered interval, as well as the horizontal line corresponding to the cost of an optimal solution to 1-S-RSP (because this cost is constant, and does not depend on F). There are two possibilities:

• g(F) and the horizontal line intersect. In that case, the intersection occurs at F ⋆ , and the solutions to 1-R-RSP(F) are less expensive for all F ≤ F ⋆ , whereas an optimal solution to 1-S-RSP is preferable for all F ≥ F ⋆ . This situation is illustrated in Figure 3.5, where the optimal objective value of 1-S-RSP is denoted by f 1-S-RSP .

• g(F) and the horizontal line do not intersect. This can happen either if the values considered for F are too low, in which case no optimal solution to 1-S-RSP is competitive compared to optimal solutions to 1-R-RSP(F), or if the considered values for F are too large, in which case no optimal solution to 1-R-RSP(F) is competitive compared to an optimal solution to 1-S-RSP.

Numerical experiments to choose between Survivable or Resilient RSP

Some numerical experiments are reported in Table 3.2. We selected two instances with 10 and 12 nodes and displayed the CPU times for Resilient RSP and Survivable RSP solved by the Branch-and-Benders-cut approach, |S i | the number of optimal solutions to 1-R-RSP(F), the F values and F ⋆ . We can see in this table that for the instance of 10 nodes, the user should choose the Resilient RSP below