Marie-Christine Costa

Cédric Bentz

Zacharie Merci

Keywords: Operations Research, Combinatorial optimization, Robust networks design, Graph theory, Mixed integer programming, Wind farm cabling networks

J'aimerais tout d'abord remercier mes directeurs de thèse:

Résumé

Aujourd'hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l'énergie. En particulier, il est devenu nécessaire d'optimiser la façon dont sont conçus les réseaux permettant de produire de l'énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d'électricité via des centrales thermiques ou nucléaires.

Nous nous intéressons dans cette thèse à la conception du câblage collectant l'énergie dans les parcs éoliens. On connaît alors la position de l'ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l'énergie doit être acheminée.

On connaît également la position des câbles que l'on peut construire, leurs capacités, et la position des noeuds d'interconnexion possibles. Il s'agit de déterminer un câblage de coût minimal permettant de relier l'ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

Mots clés: Recherche opérationnelle, Optimisation combinatoire, Conception de réseaux robustes, Théorie des graphes, Programmation en nombres entiers, Câblage de parcs éoliens.

Abstract

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms.

The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants, giving that both of those production can have harmful consequences on the environment. It has then become necessary to optimize the design and construction of such networks.

We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimization problem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.

Résumé long

Résumé long

Au 21 ème siècle, il semble que l'un des plus grands défis auxquels notre population sera confrontée est le réchauffement climatique. La température de l'air a augmenté de 1,5 degré depuis l'ère pré-industrielle et cette augmentation a été liée aux activités humaines. Presque tous les spécialistes de la communauté s'accordent à dire que la cause majeure de ce réchauffement climatique peut être attribuée à l'augmentation de la production de gaz à effet de serre (causée principalement par les émissions de monoxyde de carbone ou de méthane). Les conséquences pourraient être diverses et terribles : pour le climat (par exemple, chaleur extrême dans certaines parties du globe ou augmentation des phénomènes météorologiques extrêmes tels que tempêtes, inondations, cyclones et sécheresses) ; pour l'écosystème et la biodiversité (élévation du niveau des océans, destruction d'écosystèmes fragiles comme les récifs coralliens et la forêt amazonienne et disparition d'un grand nombre d'espèces animales) ; pour notre société et son économie (infrastructures pour s'adapter comme des installations médicales, de santé publique et capacité à alimenter la population). De nombreuses forces semblent apparaitre pour lutter contre le réchauffement climatique et impliquer l'écologie dans notre mode de vie (réduire notre consommation d'énergie, limiter le gaspillage alimentaire, optimiser la gestion des ressources, éviter de consommer des produits à forte empreinte carbone). Le développement durable, qui vise à exploiter les ressources naturelles et biologiques à un rythme qui ne conduise pas à l'appauvrissement ni même à l'épuisement mais qui permet de maintenir la productivité biologique des ressources de la biosphère, apparaît comme une orientation intéressante afin de limiter ces conséquences. En ce qui concerne la production d'électricité, les parcs éoliens, les panneaux photovoltaïques et les installations hydro-électriques semblent être des pistes intéressantes pour réduire les émissions de gaz à effet de serre.

RÉSUMÉ LONG

Aujourd'hui, la conception des réseaux est devenue une problématique décisive qui apparaît dans de nombreux domaines tels que les transports, les télécommunications ou l'énergie. En particulier, il est devenu important, voire nécessaire, d'optimiser la conception des réseaux de production, de collecte ou de transport de l'énergie. Nous nous intéressons dans cette thèse à l'électricité produite par des parcs éoliens. La production d'énergie par des éoliennes apparaît plus que jamais comme une bonne alternative à la production électrique des centrales thermiques ou nucléaires, étant donné que ces deux productions peuvent avoir des conséquences néfastes sur l'environnement. Le développement des parcs éoliens est alors un enjeu mondial et il est donc devenu nécessaire d'optimiser la conception et la construction de tels réseaux.

Nous nous concentrons dans cette thèse sur la conception du réseau de câblage qui permet de collecter et d'acheminer l'énergie produite par les éoliennes vers une sousstation, reliant le parc éolien au réseau électrique. Dans ce problème, nous connaissons l'emplacement de chaque éolienne du parc et celui de la sous-station. Nous connaissons également l'emplacement des noeuds d'interconnexion possibles qui permettent de connecter différents câbles entre eux. Chaque éolienne produit une quantité d'énergie connue et à chaque câble est associé un coût et une capacité (la quantité maximale d'énergie qui peut être acheminée par ce câble). Le problème d'optimisation que nous considérons est de choisir un ensemble de câbles de coût minimum afin que l'énergie produite par les éoliennes puisse être acheminée vers la sous-station du réseau induite par cet ensemble de câbles, sans dépasser la capacité de chaque câble. Il doit donc exister un chemin utilisant des câbles entre chaque turbine et la sous-station, mais pas nécessairement avec des noeuds d'interconnexion, qui sont des points optionnels dans le réseau.

Dans ce contexte, des pannes peuvent survenir sur les câbles ou les appareils du réseau (dues à l'environnement ou à un problème avec une turbine ou un noeud d'interconnexion par exemple). Nous nous concentrons plus précisément sur la conception de réseaux robustes (ou résilients) pour plusieurs notions robustes qui seront définies dans cette thèse.

Nous prenons en compte une certaine incertitude des données : nous considérons le cas des pannes sur les câbles ou les noeuds une fois le réseau construit (dans cette thèse nous nous concentrons sur les pannes sur les câbles, mais les pannes sur les noeuds peuvent être RÉSUMÉ LONG réduites aux pannes sur les câbles après une transformation du graphe). Nous visons alors à minimiser le coût du réseau à construire tout en respectant les contraintes de robustesse permettant de limiter les répercussions néfastes en cas de panne sur un ou plusieurs câbles du réseau.

Dans le cadre de cette thèse, nous avons été en contact avec EDF (Électricité de France), premier producteur et fournisseur d'électricité en France, via un projet PGMO (Programme Gaspard Monge pour l'Optimisation de la Fondation Mathématique Jacques Hadamard) et des ingénieurs travaillant dans le domaine des énergies renouvelables. Il semble que les aspects combinatoires et discrets de ces problèmes aient été peu étudiés jusqu'à présent chez EDF. Si la conception des réseaux de câblage présente des enjeux économiques importants, la robustesse et la résistance aux pannes sont également des critères importants. Des travaux ont également été réalisés avec la société canadienne Hatch, ce qui nous a conduit à tester nos travaux sur des données réelles (nous pouvons souligner que les parcs éoliens français sur lesquels nous travaillons avec EDF sont offshore alors que les parcs éoliens canadiens sont onshore). Dans l'environnement offshore, chaque éolienne produit à peu près la même quantité d'électricité, de sorte que l'on peut supposer que l'énergie produite par les éoliennes est uniforme.

Dans cette thèse, nous alternons entre des problèmes plus théoriques liés à la conception des réseaux de câblage de parcs éoliens en reformulant l'ensemble des contraintes électriques en contraintes de flot classiques (comme les chapitres 1, 2 et 3) et des problèmes pratiques liés aux données réelles et contraintes techniques en électricité (chapitre 4). Nous étudions des problèmes qui sont des généralisations du problème de l'arbre de Steiner : étant donné un graphe avec un ensemble de sommets, un ensemble d'arcs et un sous-ensemble de sommets appelés terminaux, ce problème vise à trouver un arbre du coût minimum couvrant tous les terminaux. Les sommets qui ne sont pas des terminaux sont appelés sommets de Steiner. Nous introduisons un sommet racine dans nos problèmes.

Dans notre application de parc éolien, les éoliennes correspondent aux terminaux, la sousstation à la racine, et les noeuds d'interconnexion aux sommets de Steiner. Notre objectif est de résoudre ces généralisations des problèmes de l'arbre de Steiner en tenant compte de la robustesse et des capacités des arcs.

RÉSUMÉ LONG

Dans le chapitre 0.2, nous présentons et définissons quelques notions, notations et méthodes utilisées dans cette thèse. Nous définissons également les problématiques étudiées.

Nous présentons quelques résultats préliminaires et résumons quelques travaux antérieurs trouvés dans la littérature.

Après discussion avec les ingénieurs d'EDF, il est apparu que les contraintes électriques peuvent être formulées comme des contraintes de flot classiques si le réseau de solutions est une arborescence. Ainsi, dans le chapitre 1, nous réduisons le problème à la recherche d'une arborescence de Steiner qui respecte les contraintes de capacité. Nous nous concentrons sur la conception des arborescences de Steiner pour lesquelles nous essayons de réduire l'impact néfaste d'une suppression d'arc dans la solution arborescente, selon plusieurs critères d'optimisation, à un coût raisonnable. Nous donnons des résultats de complexité et proposons plusieurs formulations testées sur des données réelles.

Dans nos applications de parcs éoliens, les terminaux produisent de l'énergie, donc le flot d'énergie doit être acheminé des terminaux vers la racine. Cependant, cela est strictement équivalent à considérer que l'on achemine l'énergie de la racine vers les terminaux (dans un digraphe, il suffit de prendre les arcs opposés alors qu'il n'y a aucun changement dans un graphe non dirigé). De plus, dans les applications de parcs éoliens offshore, on considère souvent que l'énergie produite par les éoliennes est uniforme, ce qui équivaut à considérer une demande unitaire et une capacité d'arc peut alors être considérée comme le nombre de terminaux qui peuvent être reliées à la racine par cet arc.

Dans cette section, nous étudions le problème de la conception de réseaux résilients à un nombre donné de suppressions d'arc. Une solution réalisable au problème que nous considérons est un réseau enraciné en une racine donnée et couvrant un ensemble donné de terminaux, et tel que, après avoir supprimé tout ensemble de k arcs, il est toujours possible de router une unité de flot de la racine vers chaque terminal (voir Sous-section 0.2. QUESTION : Trouver un sous-ensemble A ′ ⊆ A de coût minimum tel qu'il y ait un flot réalisable (c'est-à-dire respectant les capacités de l'arc) acheminant une unité de flot de r vers chaque sommet de T dans le sous-graphe de G induit par A ′ , même si un ensemble de k arcs de A ′ est supprimé.

Puisque nous considérons que nous acheminons une unité de flot de la racine vers chaque terminal, il est équivalent à considérer que la capacité u ij correspond au nombre maximum de terminaux qui peuvent être reliés à la racine par l'arc (i, j).

Afin de simplifier les formulations proposées dans les sections suivantes, nous ajoutons au graphe d'entrée un sommet s (qui correspond à un puits fictif) relié à chaque terminal t ∈ T par un arc fictif (t, s) avec c ts = 0 et u ts = 1. Ensuite, s est ajouté à V et les arcs fictifs sont ajoutés à A, et nous désignons par A I l'ensemble des arcs initiaux. Nous avons le fait suivant : Pour chaque (i, j) ∈ A, nous introduisons une variable x ij qui correspond à la quantité de flux que le défenseur choisit de faire passer par l'arc (i, j). La variable y est une variable binaire de sélection d'arc dans le réseau final. Nous introduisons également les variables binaires b ij , ∀(i, j) ∈ A : b ij = 1 si et seulement si l'attaquant choisit de supprimer l'arc (i, j). De plus, nous supposons sans perte de généralité qu'il n'y a pas d'arc entrant r.

Ensuite, nous pouvons définir le polyèdre suivant :

X (y, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∑ i∈Γ -(j) x ij - ∑ k∈Γ + (j)
x jk = 0 ∀j ∈ V \ {r, s} Par conséquent, la dualité forte tient et nous pouvons introduire le dual du problème de niveau inférieur, où µ est la variable associée aux Contraintes (1a) tandis que λ et γ sont respectivement associés aux Contraintes (1b) et (1c). Après une légère reformulation due à l'ajout de µ r et µ s , le dual peut être écrit comme suit (voir Sous-section 0.2.2 en introduction) : ∑ j∈Γ + (r) x rj , nous avons que la matrice de contraintes de (Φ) est totalement unimodulaire (parce que c'est la transposition d'une matrice totalement unimodulaire, voir Propriété 0.2.1 dans la sous-section 0.2.2 de l'introduction). Ainsi, les points extrêmes de (Φ) sont entiers. Ce problème est une formulation spéciale d'un problème de coupe minimum : µ définit les deux parties de la coupe, les variables γ et λ définissent les arcs de la coupe correspondante : pour chaque arc (i, j) dans la coupe, nous avons soit λ ij = 1 ou γ ij = 1. Nous désignons par D le polyèdre défini par deux Contraintes (3a)-(3d).

x ij ≤ u ij y ij ∀(i, j) ∈ A x ij ≤ u ij (1 -b ij ) ∀(i, j) ∈ A x ij ≥ 0 ∀(i, j) ∈ A ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (1a) (1b)
(Φ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + ∑ (i,j)∈A u ij (1 -bij )γ ij s.t λ ij + γ ij -µ i + µ j ≥ 0 ∀(i, j) ∈ A µ r = 1 µ s = 0 λ, γ ∈ [0, 1] |A| , µ ∈ [0, 1] |V | (3a) (3b) (3c)
Puisque le niveau inférieur peut être reformulé en fonction minmin en utilisant le dual décrit ci-dessus, il peut alors être réécrit comme suit :

(LL) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + u ij (1 -b ij )γ ij
L(b, γ) = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ l ∈ R |A| ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ l ij ≤ b ij ∀(i, j) ∈ A l ij ≤ γ ij ∀(i, j) ∈ A l ij ≥ γ ij -(1 -b ij ) ∀(i, j) ∈ A l ij ≥ 0 ∀(i, j) ∈ A ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭
Le niveau inférieur peut alors être réécrit comme suit:

(LL)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + u ij γ ij -u ij l ij s.t b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ) RÉSUMÉ LONG
On définit alors la fonction g: g(y, λ, γ, l) =

∑ (i,j)∈A u ij y ij λ ij + u ij γ ij -u ij l ij
On peut ensuite réécrire le programme bi-niveau comme suit: min

∑ (i,j)∈A c ij y ij s.t. g(y, λh , γh , lh ) ≥ |T | ∀h ∈ H y ∈ {0, 1} |A| (BP) b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ) (4a) (4b) (4c) (4d) (4e)
Les contraintes (4a) assurent que, pour chaque point extrême de

Conclusion

Bibliographie

List of Tables

Introduction 0.1 General introduction

In the 21 st century, it appears that the biggest challenge that will face our population is the global warming. The air temperature has been increased by 1.5 degrees since preindustrial era and this rise has been linked to human activities. Almost all specialists among the community agree that the major cause of this global warming can be attributed to the increasing production of greenhouse gas (caused by carbon monoxide emission or methane principally). The consequences could be diverse and terrible: for the climate (for example extreme heat in some parts of the globe or increase of extreme weather events like storms, floods, cyclones and droughts); for the ecosystem and the biodiversity (increase of ocean levels, destruction of fragile ecosystems like coral reef and Amazon rainforest and several extinctions of species); on our society and its economy (infrastructures to adapt like medical ones or housings, public health and capacity to feed the population). Many forces appear to fight the global warming and involve ecology in our way of life (reducing our consumption of energy, limiting the food waste, optimizing the management of resources, avoiding to consume products with a high carbon print). Sustainable development, which aims to exploit natural and biological resources at a rhythm which does not lead impoverishment or even exhaustion but makes possible the sustain of biological productivity of resources in the biosphere, comes out as a valid orientation in order to limit those consequences. Regarding the electrical production, wind farms, photo-voltaic panels and hydro-electrical facilities appear to be interesting directions in order to reduce greenhouse gas emissions.

GENERAL INTRODUCTION

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport, telecommunications or energy. In particular, it has become important and even necessary to optimize the way in which networks used to produce, collect or transport energy are designed. We are interested in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants, giving that both of those productions can have harmful consequences on the environment. The development of wind farms is then a global issue and hence it has become necessary to optimize the design and construction of such networks.

We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimization problem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. Hence there must exist a path using cables between each turbine and the substation, but not necessarily with inter-connection nodes, which are optional points in the network.

In this context, breakdowns can occur on cables or devices of the network (caused by the environment or by a problem with a turbine or inter-connexion node for example).

We focus more precisely on the design of robust (or resilient) networks for several robust notions that will be defined in this thesis. We take into account some data incertitude:

we consider the case of breakdowns on cables or nodes once the network is built (in this thesis we focus on breakdowns on cables, but breakdowns on nodes can be reduced to breakdowns on cables after a transformation of the graph). We then aim to minimize 0.1. GENERAL INTRODUCTION the cost of the network to build while respecting robustness constraints allowing to limit the damaging repercussions in case of a breakdown on one or several cables in the network.

In the context of this French wind farms we have been working on with EDF are offshore whereas Canadian wind farms are onshore). In offshore environment, each wind turbine produces about the same quantity of electricity, so we can make the assumption that the energy produced by the wind turbines is uniform.

In this thesis, we alternate between more theoretical problems related to the design of wind farm cabling networks by reformulating the set of electricity constraints into classical flow constraints (like Chapters 1, 2 and 3) and practical problems with real data and technical constraints related to electricity (Chapter 4). We study problems which are generalizations of the Steiner tree problem: given a graph with a set of vertices, a set of edges and a subset of vertices called terminals, this problem aims at finding a tree of minimum cost spanning all the terminals. The vertices which are not terminals are called Steiner vertices. We introduce a root vertex in our problems. In our wind-farm application, the wind turbines correspond to the terminals, the substation to the root, and the inter-connection nodes to the Steiner vertices. We aim at solving generalizations of Steiner tree problems taking robustness and edge capacities into account.

In Chapter 0.2, we introduce and define some notions, notations and methods used in this thesis. We also define the studied problematics. We present some preliminary results

GENERAL INTRODUCTION

and summarize some previous works found in the literature.

Following discussions with EDF engineers, it appeared that the electrical constraints can be formulated as classical flow constraints if the solution network is an arborescence.

Hence, in Chapter 1, we reduce the problem to the search for a Steiner arborescence which respects the capacity constraints. We focus on the design of Steiner arborescences for which we try to reduce the damaging impact of an arc deletion in the arborescence solution, according to several optimization criteria, at a reasonable cost. We give complexity results and propose several formulations tested on real data.

In our wind farm applications, the terminals produce energy, so the energy flow should be routed from the terminals to the root. However, it is equivalent to consider that we route the energy from the root to the terminals (in a digraph, we just have to take the opposite arcs whereas there are no changes in an undirected graph). Furthermore, in offshore wind farm applications, we often consider that the energy produced by the wind turbines is uniform, which is equivalent to consider a unit demand and an arc capacity can then be seen as the number of terminals that can be linked to the root through this arc.

In Chapter 2, we define the Capacitated Rooted k-Edge Connected Steiner Network:

given a connected graph with a root vertex, a set of terminals and integer capacity and cost on each arc of the graph, we aim to find a subset of arcs of minimum cost such that there exists a feasible flow (i.e. respecting the capacities) routing one unit of flow from the root to each terminal in the subgraph induced by those arcs, even if a given number k of arcs is deleted. This problem is equivalent to finding a robust cabling network in a wind farm, when the electricity constraints are formulated as classical flow constraints. We give several formulations, including a new bilevel formulation, study the relations between the different formulations, and test them in order to compare their efficiency.

In Chapter 3, we focus on planar graphs for the Capacitated Rooted k-Edge Connected Steiner Network. We present a method to check whether a network is resilient 0.2. PRELIMINARIES or not to the deletion of any set of k arcs using planar graph duality and shortest paths problems. We propose and describe a tabu search algorithm derived from this method.

We test our algorithm and compare its efficiency to exact methods presented in Chapter 2.

In Chapter 4, we study the real-life problem of designing a wind farm cabling network with electrical constraints of load flow. We explain the load flow study, which corresponds to a numerical analysis of the flow of electric power in an interconnected system. We must ensure that the power routed through each cable respects the electric capacities of the cable using the load flow equations to analyze the state of the electric network once the network is built. Since the load flow analysis is a non-linear system, we use an approximation in order to include them into a mixed-integer linear program. We test our algorithm on real data and give numerical results.

In a concluding chapter, we give some perspectives and future work leads.

Preliminaries

General notions in graph theory

In this section, we recall some notions from graph theory that will be used in this thesis. For more information about graph theory, the reader is referred to [START_REF] Berge | Graphes et hypergraphes[END_REF][START_REF] Brent | Introduction to graph theory[END_REF].

Formally, a directed graph (or digraph) G = (V, A) is defined by a set of vertices V and a set of arcs A ⊆ V × V . The set of predecessors (respectively successors) of a vertex v in

G is defined by Γ - G (v) (respectively Γ + G (v)). For a subset of vertices S ⊂ V in G, we define δ - G (S) = {(i, j) ∈ A | i ∈ V \S, j ∈ S} (respectively δ + G (S) = {(i, j) ∈ A | i ∈ S, j ∈ V \S})
as the set of arcs entering (resp. leaving) S. When there are no ambiguities about the related graph G, we can refer to those sets as Γ -(v), Γ + (v), δ -(S) and δ + (S), respectively.

An undirected graph G ′ = (V, E) is defined by a set of vertices V and a set of edges 0.2. PRELIMINARIES E ⊆ V × V . The set of neighbors of a vertex v ∈ V is denoted by Γ G ′ (v). For a subset of vertices S ⊂ V in G ′ , we define δ G ′ (S) as the set of edges [u, v] incident to S in G ′ (u ∈ S and v ∈ V \ S). When there are no ambiguities about the related graph G ′ , we can refer to those sets as Γ(v) and δ(S) respectively.

Two paths p 1 and p 2 in a graph are said to be arc-disjoint (edge-disjoint in an undirected graph) if there is no arc a which appears both in p 1 and p 2 . In this thesis, we will consider a special vertex r of a graph G, which is the root of the graph (i.e. there exists a path between r and every vertex of G). A graph is said to be connected if there is an undirected path between u and v for each pair of vertices u, v ∈ V 2 . In a digraph G = (V, A) (resp. an undirected graph G = (V, E)), an (i, j)-disconnecting set, with i and j two distinct vertices of V , is a set of arcs D ⊆ A (resp. a set of edges D ⊆ E) such that there are no path from i to j in the graph

G ′ = (V, A \ D) (resp. G ′ = (V, E \ D)).
A graph (respectively digraph) is said to be k-edge-connected (resp. k-arc-connected) if it remains connected (resp. strongly connected) whenever fewer than k edges (resp. arcs) are removed. Theorem 0.2.1 (k-edge-connectivity [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]]) If i and j are two vertices of a digraph (resp. undirected graph), the minimum size of an (i, j)-disconnecting set is equal to the maximum number of pairwise arc-disjoint (resp. edge-disjoint) paths from i to j. Moreover, a graph G is k-edge-connected if and only if there exist k pairwise arc-disjoint paths (resp. edge-disjoint) between each pair of vertices in G.

Flows and networks

We introduce here different notions about network flows; the reader is referred to [START_REF] Ravindra K Ahuja | Network flows: theory, algorithms, and applications[END_REF] for more information about this topic. We define a network as a digraph G = (V, A) with a non-negative capacity u ij on each arc (i, j) ∈ A, a distinguished root r ∈ V (also called source vertex) and a sink vertex s ∈ V . A flow x is a function that assigns a value x ij to each arc (i, j) ∈ A. A feasible flow satisfies the capacity constraints 0 ≤ x ij ≤ u ij for each arc (i, j) ∈ A and the conservation constraints

0.2. PRELIMINARIES ∑ u∈Γ -(v) x uv = ∑ w∈Γ + (v)
x vw for each vertex v ∈ V \ {r, s}. The value of such a flow is equal to

∑ v∈Γ + (r) x rv - ∑ u∈Γ -(r) x ur = ∑ i∈Γ -(s) x is - ∑ j∈Γ + (s) x sj .
In this thesis, we assume without loss of generality that, in any network we consider, there are no arcs entering the root r and no arcs leaving the sink s. Thus, the value of a flow x is equal to

∑ v∈Γ + (r) x rv = ∑ i∈Γ -(s)
x is . A maximum flow is defined as a feasible flow of maximum value.

In a network, for a given subset of vertices S ⊂ V with r ∈ S and s ∈ V \ S, we refer to the partition [S, V \ S] of V as an r -s cut. The cut-set associated with S is the set of arcs going from a vertex of S to a vertex of V \ S, i.e. the cut-set corresponds to δ + (S) or δ -(V \ S). The capacity of a cut (or the capacity of a cut-set) is defined as the sum of the capacities of the arcs of its cut-set, i.e. The problem of searching for a maximum flow (respectively a minimum r -s cut) in a network is called the maximum flow problem (respectively the minimum cut problem).

The flow x ij on each arc (i, j) ∈ A is not constrained to be integer. However, in this thesis we will work on integer flows because of the applications we are considering. Thus, we remind the following theorem: Theorem 0.2.3 allows to relax the integrality constraint on the value of the flow when searching for a maximum flow. We introduce the following well-known linear formulation 0.2. PRELIMINARIES for the maximum flow problem:

(M AX -F LOW ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ max x ∑ v∈Γ + (r) x rv s.t. ∑ i∈Γ -(j) x ij - ∑ k∈Γ + (j) x jk = 0 ∀j ∈ V \{r, s} 0 ≤ x ij ≤ u ij ∀(i, j) ∈ A (5a) (5b)
where the variable x ij defines for each arc (i, j) the amount of flow routed through (i, j). We introduce Remark 0.2.1:

Remark 0.2.1 If there exist two vertices i and j in V \ {r, s} such that {(i, j), (j, i)} ⊂ A and a flow defined by x such that x ij > 0 and x ji > 0, then there always exists a flow x ′ of equal value with either x ′ ij = 0 or x ′ ji = 0.

Proof: Let us suppose that a given feasible flow x assigned to a network G = (V, A) is such that there exist two vertices i and j in V such that (i, j), (j, i) ∈ A and there is a positive amount of flow on both arcs (i.e. x ij x ji > 0). By reducing the flow on both arcs by min(x ij , x ji ), we find a flow x ′ with either x ′ ij = 0 or x ′ ji = 0. The capacity constraints are obviously satisfied because we only reduce the amount of flow on two arcs and they were satisfied by x. The conservation constraints are also satisfied since we reduce the amount of flow entering and leaving both i and j by min(x ij , x ji ). Finally, the value of the flow defined by x remains the same because

∑ i∈Γ -(s) x is is not changed. □
A matrix A is said to be totally unimodular if each square submatrix of A has a determinant equal to -1, 0 or 1 (see [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]). In particular, we have that each The matrix M associated with the left-hand side of Constraints (5a) is a sub-matrix of the node-arc incidence matrix (we remove the rows associated to r and s) of a digraph.

entry of A is -1, 0 or 1.
Each column of the matrix corresponds to an arc (i, j): there is a 1 in the ith row and a -1 in the jth row and the rest of the entries of the column are 0.

Theorem 0.2.5 (Theorem 11.12 in [Ahuja, Orlin, and Magnanti 1993]) The nodearc incidence matrix M of a directed network is totally unimodular.

Following Theorems 0.2.4 and 0.2.5, we do not have to ensure that x is integer since M is totally unimodular, which yields a proof of Theorem 0.2.3.

The dual of (M AX -F LOW ) corresponds to a formulation of the minimum-cut problem and can be written as follows:

min µ,λ ∑ (i,j)∈A u ij λ ij s.t. µ v + λ rv ≥ 1 ∀v ∈ Γ + (r) µ v -µ u + λ uv ≥ 0 ∀(u, v) ∈ A, u ̸ = r, v ̸ = s -µ u + λ us ≥ 0 ∀u ∈ Γ -(s) λ ij ≥ 0 ∀(i, j) ∈ A, µ v ∈ R ∀v ∈ V \ {r, s} (6a) (6b) (6c)
It can be reformulated, with the addition of variables µ r and µ s , as follows:

(M IN -CU T ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min µ,λ ∑ (i,j)∈A u ij λ ij s.t. µ v -µ u + λ uv ≥ 0 ∀(u, v) ∈ A µ r = 1 µ s = 0 λ ij ≥ 0 ∀(i, j) ∈ A, µ v ∈ R ∀v ∈ V (7a) (7b) (7c)
In any optimal solution we have

µ v ∈ [0, 1] ∀v ∈ V , which implies λ ij ≤ 1 ∀(i, j) ∈
A. From Property 0.2.1, the transpose of a totally unimodular matrix is totally unimodular, so the matrix of constraints of (M IN -CU T ) is totally unimodular, and thus there 0.2. PRELIMINARIES exists an optimal solution (λ * , µ * ) with µ * ∈ {0, 1} |V | and λ * ∈ {0, 1} |A| . The dual problem then formulates the minimum cut problem in this way: µ defines the partition associated with the cut (we have µ v = 1 if v is in the same part as the root and µ v = 0 if v is in the same part as the sink) while λ defines the cut-set (we have λ ij = 1 if the arc (i, j) is in the cutset, i.e. µ i = 1 and µ j = 0).

In this thesis, we will consider arc-deletions in flow networks. However, vertices-deletion can be considered using the same methods by a simple transformation of the input graph.

The graph transformation is the following: we replace each vertex v of the input graph G by two vertices v 1 and v 2 and an arc (v 1 , v 2 ) in the transformed graph and each arc (u, v) is replaced by an arc (u 2 , v 1 ). The deletion of the vertex v in the input graph then corresponds to the deletion of the arc (v 1 , v 2 ) in the transformed graph (as illustrated in the example in Figure 1). For the non-oriented case, we can apply the transformation to the bi-directed graph associated to the input graph.

Steiner trees and networks

We introduce in this subsection the concepts of Steiner trees and Steiner networks (see [START_REF] Hwang | The Steiner tree problem[END_REF][START_REF] Du | Advances in Steiner trees[END_REF][START_REF] Hans | The Steiner tree problem: a tour through graphs, algorithms, and complexity[END_REF]). A tree is defined as a connected graph which is acyclic. Given an undirected graph In this thesis, we consider Steiner problems with a root and a capacity u ij on each edge [i, j] in the graph. We consider that each terminal t ∈ T has the same demand and we want to find a feasible flow (i.e. respecting the capacities defined by u and the flow conservation constraints) such that a unit of flow is routed from the root to each terminal:

G = (V,
each terminal can hence be seen as a sink. We say that a feasible flow x routes one unit of flow from the root r to each terminal if the flow conservation constraints are as follows:

∑ k∈Γ + (j)
x jk -

∑ i∈Γ -(j) x ij = ⎧ ⎪ ⎨ ⎪ ⎩ |T | if j = r -1 if j ∈ T 0 otherwise ∀j ∈ V
If we add to the graph a fictive sink s with an edge (t, s) of capacity u ts = 1 for each terminal t ∈ T , our problem is equivalent to finding a feasible (r -s)-flow of value |T |.

Previous work

We summarize in this section the existing results in the literature for problems which are related to the ones studied in this thesis.

Wind farm cable layout optimization

The design of wind farms brings several challenges in optimization: one can think of the optimization of the location of each wind turbine (a literature review for this kind of problems is proposed by Gonzalez et al. [González, Payán, Santos, and González-Longatt 2014]) or of the connection between the electric network and the wind farm [START_REF] Qi | Joint planning of energy storage and transmission for wind energy generation[END_REF], for example. In this thesis, we will only consider the problem of designing the cabling network that collects the energy produced by the wind turbines and route it to the sub-station, once the locations of the different wind turbines are known.

Problems of designing the wind farm cabling network have already been studied in the literature. Hertz et al. [Hertz, Marcotte, Mdimagh, Carreau, and Welt 2012] study a real-life problem with real data for onshore wind farms, where several cable types are available (subterranean or not). Furthermore, the energy produced by the wind turbines and routed to the sub-station is non-splittable: once the energy is routed through a same cable, it cannot be split and must be routed to the sub-station through the same path (i.e.

if a "chunk" of energy E is routed from u to v through the same cable with v different from the substation, there exists a node w such that the "chunk" E is entirely routed from v to w). The authors give mixed integer formulations and propose a cutting plane generation method allowing to evaluate their algorithm on real data.

Other authors propose mixed integer formulations for the design of wind farm cabling [START_REF] Berzan | Algorithms for cable network design on large-scale wind farms[END_REF][START_REF] Fagerfjäll | Optimizing wind farm layout: more bang for the buck using mixed integer linear programming[END_REF]]. Regarding offshore wind farms, Pillai et al. [Pillai, J, L, M, and de Laleu V 2015] propose a set of algorithms computing approximate solutions in order to optimize successively the location of the wind turbines and the design of the wind farm cabling network considering natural obstacles related to the environment. [START_REF] Fischetti | Optimizing wind farm cable routing considering power losses[END_REF]] also consider natural obstacles related to the environment but they additionally consider the power losses related to the routing of electricity. They propose a mixed-integer formulation and a method allowing to find good approximate solutions using matheuristics.

PREVIOUS WORK

To the best of our knowledge, there does not exist literature proposing a method that could be applied to the problem of designing wind farm cabling networks with resilience to breakdowns on cables and load flow constraints. In this thesis, we are interested in the design of wind farm networks with such constraints.

Steiner arborescence problems

In some cases, production rules and electrical constraints related to the routing of electricity imply that the problem of designing such a wind farm cabling can be seen as the search for a Steiner arborescence with capacity constraints and unitary demands. More precisely, the problem can be defined as follows: we are given a graph with a subset of vertices T and a root r, where each arc has a cost and a capacity. We look for an arborescence rooted at r which contains each vertex of T , and such that, for each arc (i, j) of the arborescence, the number of terminals in the sub-arborescence rooted at j is at most equal to the capacity of (i, j). The problem is then a generalization of the Steiner arborescence problem, but also a particular case of the generalized Steiner arborescence, in which there is a fixed demand at each terminal and each arc capacity corresponds to the quantity of demands which can be routed through this arc.

The minimum-cost (or weighted) Steiner tree problem (without capacity constraints) has been widely studied in the literature; the reader is referred to [START_REF] Du | Advances in Steiner trees[END_REF][START_REF] Hwang | The Steiner tree problem[END_REF][START_REF] Hans | The Steiner tree problem: a tour through graphs, algorithms, and complexity[END_REF]. It has also many applications in industry; see [START_REF] Du | Steiner tree problems in computer communication networks[END_REF][START_REF] Cheng | Steiner trees in industry[END_REF]]. This problem is N P-hard even if all edge costs are equal (it corresponds to the Minimum Steiner Tree Problem) and if G is planar [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. However, if the number of terminals is fixed, this problem can be solved in polynomial time [START_REF] Stuart | The steiner problem in graphs[END_REF]. each terminal has a specific amount of demand that must be routed from the root to this terminal, and the capacity of an arc corresponds to the maximum amount of demands that can be routed through this arc.

To the best of our knowledge, the design of Steiner trees with constraints of robustness, i.e. where we aim to design trees which are not too much impacted by arc deletions, has not been studied. However, different problems with arc deletions on trees have been studied. [START_REF] Bazgan | Efficient determination of the k most vital edges for the minimum spanning tree problem[END_REF] study the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree: they propose an enumeration algorithm and a MIP to solve the problem. This problem has been shown to be N P-hard, and approximation algorithms have been proposed [START_REF] Greg | Increasing the weight of minimum spanning trees[END_REF][START_REF] Liang | Finding the k most vital edges with respect to minimum spanning trees for fixed k[END_REF]]. However, this problem considers the arc deletions before the design of the tree, whereas we consider the arc deletions during the design of the tree.

Robust Steiner networks

Robust problems have been widely studied in continuous optimization [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF][START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF][START_REF] Beyer | Robust optimization-a comprehensive survey[END_REF] and can be seen as problems modeling uncertainty, where the description of uncertainty is a 0.3. PREVIOUS WORK deterministic variability of data or parameters. In this thesis, we consider an uncertainty on the arcs (or cables in our application on wind farms): an arc can be deleted or not.

The robust aspect of "worst-case minimization" that we consider can be seen as the one proposed by Bertsimas and Sim [START_REF] Bertsimas | The price of robustness[END_REF], who set an upper bound on the total data uncertainty (budget of uncertainty).

More precisely, we address problems of designing networks in which we consider the possibility of arc deletion: in our application, it corresponds to taking into account the risk of a breakdown on one or several cables after the construction of the wind farm cabling network. We estimate a budget of arc deletions k: there can be at most k simultaneous arc deletions in the network (i.e. k breakdowns at the same time). The problem is then to design a network which is still functional after the deletion of any set of k arcs.

In the literature, problems of designing survivable networks have been studied; the term has been introduced by Steiglitz et al. [START_REF] Steiglitz | The design of minimum-cost vable networks[END_REF]. Given a graph G = (V, E) and a cost function on E, the problem consists in finding a subgraph of G of minimum cost which respects some connectivity constraints. However, these connectivity constraints can be defined in several ways in the literature.

On the one hand, it is possible to define a matrix R = [r ij ]: a feasible solution must then contain r ij disjoint paths between each pair of vertices i and j. On the other hand, connectivity requirements can be defined by a connectivity value r v given for each vertex v, and we have to ensure that we have min(r i , r j ) disjoint paths for each pair of vertices i and j. In order to well dissociate the two problems, we refer to the first one as the Network Design Problem with Connectivity Requirements (NDC) [START_REF] Thomas | Strong formulations for network design problems with connectivity requirements[END_REF] and to the second one as the Survivable Network Problem (SNP) [START_REF] Steiglitz | The design of minimum-cost vable networks[END_REF]. SNP is trivially a special case of NDC. Furthermore, the definition of both problems can vary if we consider vertex-disjoint or edge-disjoint (or arc-disjoint in directed graphs) paths. Those problems generalize well-studied problems such as the minimum spanning tree (when all requirements are equal to 1), the minimum Steiner tree 0.3. PREVIOUS WORK (when all requirements are equal to either 1 or 0) or the design of k-connected graphs at minimum cost (when all requirements are equal to 0 or a given integer k).

Goemans and Bertsimas consider SNP in the case of edge-disjoint paths when the input graph is complete [Goemans and [START_REF] Michel | Survivable networks, linear programming relaxations and the parsimonious property[END_REF]. They give problem formulations and properties on the structure of the continuous relaxation. They also propose a heuristic which is based on solving several Steiner tree problems. This heuristic ensures a cost value of at most 2 min(log R, p) times the cost of an optimal solution, where R is the highest connectivity requirement and p is the number of non-zero values in the connectivity requirements.

Raghavan [START_REF] Raghavan | Formulations and algorithms for network design problems with connectivity requirements[END_REF]] proposes a dual-ascent algorithm and new formulations for NDC in the case of both vertex-disjoint and edge-disjoint paths. Williamson et al.

[ [START_REF] David P Williamson | A primaldual approximation algorithm for generalized steiner network problems[END_REF] give an approximation algorithm running in polynomial time with an approximation radio equal to 2R (where R is defined as previously), which has been enhanced afterward by Gabow et al. who propose an algorithm with a better time complexity [START_REF] Harold N Gabow | An efficient approximation algorithm for the survivable network design problem[END_REF]]. Agrawal et al. [START_REF] Agrawal | When trees collide: An approximation algorithm for the generalized steiner problem on networks[END_REF] propose an approximation algorithm for NDC in the case of arc-disjoint paths with a ratio equal to 2 log R when considering that an arc of the input graph can be selected several times in a solution.

Grötschel et al. [START_REF] Grotschel | Design of survivable networks[END_REF] give properties on the structure of an optimal solution for NDC allowing to design efficient heuristics. They also study the this problem but do not take into account capacities, and use the connectivity requirement function r like in SNP [START_REF] Grotschel | Design of survivable networks[END_REF]. In our case, the connectivity requirement can be seen as using the requirement matrix R = [r ij ] as in the case of NDC, with the restriction that for each terminal t, we have r rt = k + 1 (where r denotes the root vertex), and the value of each other entry in R is 0. Several authors take into account capacities by considering a cost of allocation, whereas we consider fixed capacities [START_REF] Bienstock | Strong inequalities for capacitated survivable network design problems[END_REF][START_REF] Rajan | A directed cycle-based column-and-cut generation method for capacitated survivable network design[END_REF]. Studies on more generalized problems with multi-commodity flows have also been considered [START_REF] Dahl | A cutting plane algorithm for multicommodity survivable network design problems[END_REF][START_REF] Stoer | A polyhedral approach to multicommodity survivable network design[END_REF]. There also exist studies of those problems in particular graphs without the existence of root or the capacity constraints [START_REF] Baïou | Steiner 2-edge connected subgraph polytopes on series-parallel graphs[END_REF][START_REF] Biha | Steiner k-edge connected subgraph polyhedra[END_REF]. In this thesis we study the design of networks resilient to a given number of arc-deletions and a single-source defined by the root, while taking fixed capacities into account, whereas in the literature capacity allocation has been studied.

The k most vital arcs in flow networks and network interdiction problems

Given a network with arc capacities, a root (or source) vertex r and a sink vertex s, the problem of finding a subset of k arcs such that the deletion of these k arcs results in the maximum decrease of the value of the maximum flow between r and s can be referred as the k Most Vital Arcs Problem in Flow Networks (k-MVAPFN).

PREVIOUS WORK

Lubore et al. [START_REF] Stephen H Lubore | Determining the most vital link in a flow network[END_REF] and Wollmer [START_REF] Richard | Some methods for determining the most vital link in a railway network[END_REF] give fast algorithms for the case where k = 1 using a sequence of maximum flow problems. Barton [START_REF] Barton | Addressing the problem of finding a single vital edge in a maximum flow graph[END_REF]] proposes more efficient algorithms to solve the same problem for particular graphs like acyclic graphs.

Ratliff et al. [START_REF] Bibliography H Donald Ratliff | Finding the n most vital links in flow networks[END_REF] introduce the problem for a non-fixed value of k. The problem has been generalized into the network interdiction problem by

Wood [START_REF] Wood | Deterministic network interdiction[END_REF]]: he considers a deletion cost associated with each arc and a budget B of deletion, the sum of the deletion costs of the arcs which are deleted must not exceed the budget B. Obviously, k-MVAPFN is a special case of the network interdiction where B = k and all deletion costs are equal to 1. He shows that the problem is strongly N P-hard for both k-MVAPFN and the network interdiction problem, and proposes a mixed-integer formulation. This problem has several applications [START_REF] Assimakopoulos | A network interdiction model for hospital infection control[END_REF][START_REF] Pm Ghare | Optimal interdiction policy for a flow network[END_REF][START_REF] Salmeron | Analysis of electric grid security under terrorist threat[END_REF].

On planar graphs, the problem becomes weakly N P-complete: Phillips [START_REF] Phillips | The network inhibition problem[END_REF] and Zenklusen [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF]] propose algorithms using planar graph duality to solve the problem in pseudo-polynomial time. We present in this thesis a tabu search using an extension of those results in order to check whether a solution is feasible or not.

Chapter 1

Robust arborescences 1.1 Introduction

In this chapter, we focus on finding a robust Steiner or spanning arborescence covering the root and the terminals of G. Here, the robustness consists in finding a solution which minimizes the number of terminals disconnected from the root in the worst case of an arc failure.

This setting arises in some wind farm cabling problems, when technical constraints impose that all electrical flows arriving at any device except the substation must leave it through one and only one cable: an inclusion-wise minimal sub-network of G respecting those constraints then corresponds to a Steiner anti-arborescence. The wind turbines are identical, and the wind is assumed to blow uniformly, so we can assume without loss of generality that each turbine produces one unit of energy. Then, A is the set of all possible cable locations, r is the sub-station collecting the energy and delivering it to the electric distribution network, T represents the set of nodes where a wind turbine lies, and

V \ ({r} ∪ T )
is the set of Steiner nodes, corresponding to possible junction nodes between cables. In that case, the flow is routed from the vertices of T to r, and we search for an anti-arborescence. However, the problem is easily seen to be equivalent to the Steiner arborescence problem, by reversing the flow circulation in the solution.

We begin by defining the problem and giving some complexity results, and then we

DEFINITION OF PROBLEMS AND COMPLEXITY RESULTS

propose mathematical formulations which are tested on real wind farm instances.

Definition of problems and complexity results

We assume in this section that the graph G = (V, E) is undirected. We define the robust problem without capacity constraints as follows:

Robust Steiner Arborescence problem (RStA)

INSTANCE: A connected graph G = (V, E, r, T ) with r ∈ V and T ⊆ V \ {r}. PROBLEM: Find an arborescence S = (V S , A S ) such that V S ⊆ V , A S ⊆ E and T ⊂ V S ,
which is rooted at r and minimizes the number of terminals disconnected from r when an arc a is removed from A S , in the worst case.

We also consider the spanning version of the problem (i.e., T = V \ {r}). In this case, the problem is to minimize the number of vertices in the largest (regarding the number of vertices) subarborescence not containing r. We define it as follows:

Robust Spanning Arborescence problem (RSpA)

INSTANCE: A connected graph G = (V, E, r) with r ∈ V .
PROBLEM: Find a spanning arborescence S of G, rooted at r, which minimizes the size of the largest subarborescence of S not containing r.

Obviously, the largest subarborescence not containing r is rooted at a vertex v ∈ Γ G (r), and the worst case is the failure of an arc incident to the root. We have the following property:

Property 1.2.1 a) There is an optimal solution S * of RSpA containing (r, v) for all

v ∈ Γ G (r) (Γ G (r) = Γ + S * (r)). b) There is an optimal solution S * = (V * , A * ) of RStA containing (r, v) for all v ∈ V * ∩ Γ G (r).

DEFINITION OF PROBLEMS AND COMPLEXITY RESULTS

Proof: Let S = (V, A S ) be an optimal solution of RSpA such that there is QUESTION: Is there a spanning arborescence S = (V S , A S ) of G, rooted at r, such that the size of any subarborescence of S not containing r is at most β?

v ∈ Γ G (r) with (r, v) / ∈ A S ,
Theorem 1.2.1 RSpAF is NP-Complete.
Proof: We introduce the 3-Partition problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] in order to transform an instance of this problem into a RSpAF one.

3-Partition problem

INSTANCE: A finite set D of 3m positive integers d i , i = 1, ..,
d i -1 successors in S.
Finally, the constraints B/4 < d i < B/2 imply that, ∀j = 1, ..., m, v j is connected to exactly 3 vertices w i denoted in the following by w j 1 , w j 2 and w j 3 , and

such that |S(w j 1 )| + |S(w j 2 )| + |S(w j 3 )| = |S(v j )| -1 = B.
Then, it is easy to obtain a solution to the 3-Partition instance. For each j = 1, .., m,

we set M j = {|S(w j 1 )|, |S(w j 2 )|, |S(w j 3 )|} = {d j 1 , d j 2 , d j 3 }.
We have m disjoint sets, each of size B, which cover exactly D. For the instance given in Figure 1.1, a solution to 3-Partition can be associated with the arborescence given in thick: M 1 = {5, 3, 3} and

M 2 = {4, 4, 3}.
Moreover, from a solution to the 3-Partition instance, it is easy to obtain a solution S where the demand at each node is an integer (our demands are all equal to 1), and hence from Theorem 1.2.1 we obtain the following corollary: , r, d, u) where d represents the (integral) demands at each node and u the capacities of the edges, the problem of deciding whether there exists a spanning arborescence of G, rooted at r and respecting the capacities, is NP-Complete (even if u is a uniform function and all demands are equal to 1).

Corollary 1.2.2 Given a graph G = (V, E

MATHEMATICAL FORMULATIONS AND TESTS

This extends the following result due to Papadimitriou [START_REF] Papadimitriou | The complexity of the capacitated tree problem[END_REF]]: given two positive values C and K and a graph G = (V, E, r, c) where c is a cost function on the edges, the problem of deciding whether there exists a spanning arborescence S of G rooted at r, such that each subarborescence of S not containing r contains at most K vertices, and with total cost at most C, is NP-Complete.

The complexity results given in this section concern undirected graphs, and so the more general case of directed graphs too, since an undirected graph can be transformed into a directed one by replacing each edge by two opposite arcs. If we consider problems with capacity constraints, we give the same capacity to both opposite arcs: since we search for an arborescence, only one of them will appear in the solution.

In the following, we study the more general following problem, which is hence also NP-hard:

Robust Capacitated Steiner Arborescence problem (RCStA) PROBLEM: Find an arborescence S = (V S , A S ) with V S ⊆ V and A S ⊆ E, rooted at r and spanning the terminals of T , which respects the arc capacities and minimizes the number of terminals disconnected from r when an arc a is removed from A S , in the worst case.

INSTANCE: A connected graph G = (V, E, r, T, u) with r ∈ V , T ⊆ V \ {r}

Mathematical formulations and tests

In this section we propose formulations for robust Steiner problems where the robustness is considered either as a constraint with the objective of minimizing the cost, or as an objective with or without constraints on the cost. Moreover, we study two kinds of robustness by considering worst or average consequences of breakdowns.

MATHEMATICAL FORMULATIONS AND TESTS

Let G = (V, A, r, T, u, c) be a directed graph with a vertex set V , an arc set A, a root r, a set of terminals T , and capacity and cost functions, respectively denoted by u and c, on the arcs. As seen before, if G is undirected, then we replace each edge by two opposite arcs with the same capacity and cost. To formulate the different problems, for each arc (i, j) ∈ A we introduce the 0-1 variable y ij and the integer variable x ij , where y ij equals 1 if and only if the arc (i, j) is selected in the solution, and x ij represents the number of terminals connected to the root through the arc (i, j), or equivalently the number of terminals in the subarborescence rooted at j. We introduce the following polyhedron T :

T = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x ∈ N |A| , y ∈ {0, 1} |A| ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ∑ (i,j)∈A x ij - ∑ (j,k)∈A x jk = ⎧ ⎪ ⎨ ⎪ ⎩ |T | if j = r -1 if j ∈ T 0 otherwise ∀j ∈ V ∑ (i,j)∈A y ij ≤ 1 ∀j ∈ V \ {r} x ij ≤ u ij y ij ∀(i, j) ∈ A ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭
In the following, we write (x, y) ∈ T when we consider a couple of variables verifying the constraints of T . The first set of constraints in T ensures both the conservation of the number of terminals connected through each Steiner vertex j ∈ V (flow conservation)

and the connection of the root to all terminals. The second set of constraints ensures that the solution is an arborescence, i.e., that each vertex has at most one predecessor.

Finally, the third set ensures that there is no flow on a non existing arc, and that the number of terminals connected through an arc (i, j) ∈ A does not exceed its capacity. In the following, the relative gap between two costs will be denoted by ∆. The well-known problem of the Capacitated Steiner Arborescence (CStA) can be formulated as follows [START_REF] Bousba | Finding minimum cost directed trees with demands and capacities[END_REF]:

CStA ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T ∑ (i,j)∈A c ij y ij
As explained previously, we evaluate the robustness of a Steiner tree by considering

MATHEMATICAL FORMULATIONS AND TESTS

the number of terminals disconnected from the root in the worst scenario, that is, the maximum number of terminals connected through an arc incident to the root, which is equal to max j∈Γ + G (r) x rj . Let R be a fixed bound on this value: we may disconnect at most R terminals from the root by deleting an arc. We propose the following formulation for the Capacitated Steiner Arborescence with bounded robustness (CStA bounded-robust ):

CStA bounded-robust ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T ∑ (i,j)∈A c ij y ij s.t. x rj ≤ R ∀j ∈ Γ + (r)
Let us now consider the robustness as an objective. Note that the default objective function is to minimize the cost of the solution. If a model uses another objective function, then its name will start by a given letter, e.g., R if we want to optimize the worst-case robustness. We propose the following formulation for RCStA:

RCStA ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T max j∈Γ + G (r)
x rj

The max function is handled in our formulation with the addition of a variable η with η ≥ x rj ∀j ∈ Γ + G (r): the objective function is then to minimize η. Since this formulation does not take the cost into account, we also propose a new formulation where we bound the cost of a solution by a given value C:

RCStA bounded-cost ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T max j∈Γ + G (r)
x rj s.t.

∑ (i,j)∈A c ij y ij ≤ C
The max function is handled in RCStA bounded-cost in the same way than in RCStA.

However, the previous models only consider the worst-case of a breakdown. It appears that it could also be interesting to "balance" the tree in order to reduce the loss due to an "average breakdown". To this end, we consider arc failures at each vertex and not only at the root, i.e., for each i ∈ V , we consider the worst case of a breakdown of an arc leaving

MATHEMATICAL FORMULATIONS AND TESTS

i. This corresponds, for each i ∈ V , to the maximum number of terminals that cannot be reached from the root in case of a breakdown of an arc (i, j), j ∈ Γ + G (i), or equivalently to the maximum flow on an arc (i, j), j ∈ Γ + G (i). We define the "balanced robustness" as the sum of these values:

∑ i∈V max j∈Γ + G (i) x ij .
This function appears to be an alternative formulation of the losses in both the worst and the average breakdown robustness.

We will use the letters BR to refer to models where one wants to optimize the balanced robustness. We propose formulations similar to the previous ones for the Capacitated Steiner Arborescence with bounded balanced robustness, where we bound the balanced robustness of a solution by a given value BR:

CStA bounded-balanced_robust ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T ∑ (i,j)∈A c ij y ij s.t. ∑ i∈V max j∈Γ + G (i) x ij ≤ BR
The max function in the constraint is handled in CStA bounded-balanced_robust with the addition of |V | variables β i for each vertex i of V with β i ≥ x ij ∀j ∈ Γ + G (i): the sum of the variables β i with i ∈ V must then not exceed BR.

The following formulation aims at computing the best balanced robustness:

BRCStA ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T ∑ i∈V max j∈Γ + G (i) x ij
The max function is handled in BRCStA in a similar way than in CStA bounded-balanced_robust :

we minimize the sum of the variables β i instead of setting an upper bound to this sum.

Moreover, we can keep this latter objective while bounding both the worst-case robustness (by R) and the cost of the solution (by C). We obtain:

MATHEMATICAL FORMULATIONS AND TESTS

BRCStA bounded-robust-cost ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min (x,y)∈T ∑ i∈V max j∈Γ + G (i) x ij s.t. x rj ≤ R ∀j ∈ Γ + G (i) ∑ (i,j)∈A c ij y ij ≤ C
The max function in the objective function of BRCStA bounded-robust-cost is handled in the same way than in BRCStA.

We tested those formulations on real wind farm data sets. Even if the number of instances is small, the results are interesting to analyze, and we can compare the robustness, costs and structures of the solutions. Data parameters and results are available respectively in Tables 1.1a and 1.1b. In the same way, let BR * be the best balanced robustness (optimal value of BRC-StA, not given in the table); see Figure 1.4 for the associated solution on the test instance.

MATHEMATICAL FORMULATIONS AND TESTS

The cost of a solution with the best balanced robustness, denoted by C * BR * , is obtained by solving CStA bounded-balanced_robust with BR = BR * , and ∆ Cbrob = (C * BR * -C * )/C * represents the "cost of balanced robustness", i.e., the percentage of augmentation of the cost of a non robust arborescence to get a balanced robust solution.

We also study the behavior of the robustness when we bound the cost to a value close to the one of an optimal non robust arborescence : R 8 (resp. R 12 ) corresponds to the optimal value of RCStA bounded-cost with a bound C = 1.08C * (resp. C = 1.12C * ).

We now analyze the results. The cost of robustness is quite variable on those instances (from 9 to 24%) but remains rather low. On the contrary, we can see that the optimization of the average robustness is way more expensive (raise from 33% to 64% of the cost) because it involves significantly more edges (see Figure 1.4).

As we can see on Table 1.1b, a cost augmentation of 8% or 12% on the optimal cost can result in a solution with a good value of worst-case robustness for some instances: instances 2 and 4 present an excellent value of such robustness with only a cost augmentation of 8%, while instances 1 and 3 have a rather good one with a cost augmentation of 12%.

Finally, we compare the optimal robustness R * to the robustness of the balanced arborescence S b obtained by solving BRCStA, i.e., we compute in S b (see Figure 1.4) the maximum number of terminals which are disconnected after the deletion of an arc incident to the root. Let R BR * be this number, shown in the last column of Table 1.1b. For the test instances, the values of R * and R BR * are the same, which means that S b is a good solution for both the worst and balanced robustness, but we have seen before that its cost is high. Indeed, for these instances, we see that forcing a solution with R = R * to be optimally balanced increases the cost by at least 33 %. Nevertheless, there is no guarantee in the general case that the best balanced solution also has the best robustness in the worst case, although the arcs incident to the root are involved in the computation of the balanced robustness. 1.4), the balanced robustness is optimal and the robustness in the worst case is fine, but the cost can be really high (a raise of the optimal cost to 64% on those data sets). Adding bounds on both cost and worst-case robustness, while minimizing the balanced robustness (see BRCStA bounded-robust-cost in Figure 1.5), yields a solution which has both a reasonable cost and a really good worst-case and balanced robustness, and hence it seems that it actually yields the best compromise between the three optimization criteria (the cost and the two types of robustness considered here).

Definitions and notations

In this section, we study the problem of designing networks which are resilient to a given number of arc-failures. A feasible solution to the problem we consider is a network rooted at a given root and covering a given set of terminals, and such that, after deleting any set of k arcs, it is still possible to route a unit of flow from the root to each terminal (see Subsection 0.2.3 in the introduction), while respecting given capacities on the arcs.

Formally, we define the following problem:

Capacitated Rooted k-Edge Connected Steiner Network problem (CRkECSN)

INSTANCE: A connected digraph G = (V, A, r, T, u, c) with a set of vertices V , a set of arcs A, a root r ∈ V , a set of terminals T ⊆ V \ {r}, an integer capacity function u on A, a cost function c on A, an integer k with 1 ≤ k ≤ |A| -1.
QUESTION: Find a subset A ′ ⊆ A of minimum cost such that there is a feasible flow (i.e. respecting the arc capacities) routing a unit of flow from r to each vertex of T in the subgraph of G induced by A ′ , even if any set of k arcs in A ′ is deleted.

DEFINITIONS AND NOTATIONS

Since we consider that we route one unit of flow from the root to each terminal, it is equivalent to consider that the capacity u ij corresponds to the maximum number of terminals that can be linked to the root through the arc (i, j). In order to simplify the formulations proposed in the next sections, we add to the input graph a vertex s (which corresponds to a fictive sink) connected to every terminal t ∈ T by a fictive arc (t, s) with c ts = 0 and u ts = 1. Then, s is added to V and the fictive arcs are added to A, and we denote by A I the set of initial arcs (see Figure 2.1 for an example).

We have the following fact: For any partition of V \ {s} into two parts S 1 and V \ ({s} ∪ S 1 ) with r / ∈ S 1 and

S 1 ∩ T ̸ = ∅, we must have that ∑ (i,j)∈δ -(S 1 ) u ij ≥ |S 1 ∩ T | in
order to allow the routing of a unit of flow from the root to each terminal (we remind that δ -(S 1 ) is the set of arcs entering S 1 , see Subsection 0.2.1). In the transformed graph, for any partition of V into two parts S 2 and V \ S 2 with r / ∈ S 2 and s ∈ S 2 , we must have that

∑ (i,j)∈δ -(S 2 ) u ij ≥ |T | (any cut
must have a capacity at least equal to |T | or equivalently there exists a r -s flow of value |T |) in order to be able to route a unit of flow from the root to each terminal. In the example proposed in Figure 2.1, we have T = {t 1 , t 2 , t 3 } and we call u i the capacity of the arc e i for i = 1, .., 8. If we take S 1 = {r, v 1 , t 1 }, in the input graph we must have that u 3 + u 4 ≥ 2 while in the transformed graph we must have u 3 + u 4 + u 8 ≥ 3. Since e 8 is a fictive arc, we have u 8 = 1, thus the constraints are equivalent.

Formulations

Cutset formulation

We introduce, for each (i, j) ∈ A, a binary variable y ij equal to 1 if the arc (i, j) is selected in A ′ , 0 otherwise. In this chapter, the variable y is defined for different formulations and for each one, y ts is set to 1 for each terminal t ∈ T : the fictive arcs will always be selected in the final network (furthermore their cost is equal to 0 and they cannot fail).

Consider the r -s cuts [V \ V S , V S ] with V S ⊂ V , r ∈ V \ V S , s ∈ V S and V S ̸ = {s},

FORMULATIONS

and let S be the set of all the associated cut-sets S in A, i.e. S = δ -(V S ) for each V S . S is the set of r -s cutsets except the one containing only fictive arcs. Notice that if S ∈ S then S ∩ A ′ is a cut-set in the selected network. For any set S ∈ S, let C S k be the set of subsets of S of size k of non-fictive arcs. Please note that there are always at least k + 1 non-fictive arcs in S because, from Remark 2.1.1, C S k cannot be empty. For each S ∈ S, we define M S as the maximum capacity of a subset of k selected arcs of S:

M S = max C∈C S k ∑ (i,j)∈C u ij y ij (2.1)
M S corresponds to the maximum capacity that can be lost in the cut-set S after the deletion of k arcs. We propose the following cutset formulation:

(CU T ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y ∑ (i,j)∈A c ij y ij s.t. ∑ (i,j)∈S u ij y ij -M S ≥ |T | ∀S ∈ S y ij ∈ {0, 1} ∀(i, j) ∈ A (2.2)
Constraints (2.2) ensure that, for each cut, the capacity of the cut after the worst-case deletion of k arcs of the cut-set is at least equal to the number of terminals, i.e., one can still route |T | units of flow from r to s while respecting the capacity constraints. They are necessary to every feasible solution. Indeed, they ensure that, for each cut-set in the graph induced by the arcs (i, j) such that y ij = 1, the capacity of the cutset minus the k maximal arc capacities of the cut is greater than or equal to the number of terminals

∑ (i,j)∈S\C u ij y ij ≥ |T | ∀S ∈ S, ∀C ∈ C S k (2.
3)

The number of Constraints (2.3) is obviously bigger than the number of Constraints (2.2). The number of Constraints (2.3) being exponential, we propose a constraints generation algorithm. We begin with a small number of Constraints (2.3), associated with a small subset of S. We obtain a lower bound for our problem. Then we search for a cut-set that does not verify some constraint (2.3) by solving the following subproblem: given a network induced by the arcs (i, j) such that ŷij = 1 (where ŷ is the current value of y),

we aim to find a cut-set S of minimum residual capacity once we delete its k most capac-

(CU T -SEP ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min s,b,v ∑ (i,j)∈ Â u ij s ij s.t s ij + b ij -v i + v j ≥ 0 ∀(i, j) ∈ Â v r = 1 v s = 0 ∑ (i,j)∈ Â b ij ≤ k ∑ t∈T b ts = 0 s ij , b ij ∈ {0, 1} ∀(i, j) ∈ Â, v ∈ {0, 1} |V | (2.4a) (2.4b) (2.4c) (2.4d) (2.4e) (2.4f)
In this MIP, the variable v defines a r -s-cut on the network: any vertex j with v j = 1 is in the same part of the cut as r, and any vertex i with v i = 0 is in the same part as s.

FORMULATIONS

The variables b ij and s ij are binary and we have b ij = 1 if and only if arc (i, j) is deleted, whereas s ij defines the selection of (i, j) in the cut-set: s ij = 1 if and only if the arc (i, j)

is selected in the cut-set. Constraints (2.4a) ensure that S = {(i, j) s.t.

s ij = 1 or b ij = 1}
defines a cutset in the current network Ĝ (if b ij = 1, we have s ij = 0 in any optimal solution because of the minimization of the objective function), and the objective function

∑ (i,j)∈ Â u ij s ij
represents the residual capacity of S, i.e., the capacity of the undeleted arcs of S. Constraints (2.4b) and (2.4c) ensure that the root and the sink are not in the same part of the cut. Constraints (2.4d) and (2.4e) ensure that there are no more than k arc deletions, and that no fictive arc can be deleted. If the solution provides a cutset with a residual capacity at least equal to |T |, then the solution is feasible. Otherwise, we add the associated constraint to the main MIP.

In the case of a uniform capacity U on each arc a ∈ A I , M S in Constraints (2.2) becomes a constant equal to kU and hence these constraints are linear, which implies that Constraints (2.3) are useless. The number of constraints is still exponential, but highly reduced compared to the non-uniform case. The formulation can be rewritten as follows:

min y ∑ (i,j)∈A c ij y ij s.t. ∑ (i,j)∈S u ij y ij ≥ |T | + kU ∀S ∈ S y ij ∈ {0, 1} ∀(i, j) ∈ A (2.5)

Undirected graphs

Adapting the formulation to the undirected case where we are given a set of edges E instead of a set of arcs A is quite straightforward. Indeed, it can be done by considering the undirected cut-sets of the graph instead of the directed ones.

Flow formulation

In this section, we introduce a formulation based on flow variables. We define F as the set of all possible arc-failure scenarios: it corresponds to the set of all k-combinations

FORMULATIONS

in A I . We introduce the variable x F ij which represents the amount of flow routed through the arc (i, j) ∈ A when the scenario F ∈ F occurs (we have x F ij = 0 if (i, j) ∈ F ). The variable y is defined as in the previous formulation (see Subsection 2.2.1). We propose the following flow formulation:

(F LOW ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min x,y ∑ (i,j)∈A c ij y ij s.t. ∑ i∈Γ -(j) x F ij - ∑ k∈Γ + (j) x F jk = 0 ∀j ∈ V \ {r, s}, ∀F ∈ F ∑ t∈Γ -(s) x F ts = |T | ∀F ∈ F x F ij ≤ u ij y ij ∀(i, j) ∈ A, ∀F ∈ F x F ij = 0 ∀F ∈ F, ∀(i, j) ∈ F x ∈ R |A|×|F | + , y ∈ {0, 1} |A| (2.

Undirected graphs

In order to adapt the formulation to the undirected case with a set of edges E instead of a set of arcs A, one can define for each [i, j] ∈ E the variables y ij , x F ij and x F ji . The function Γ + and Γ -are replaced by the function Γ in Constraints (2.6a) and (2.6b), while Constraints (2.6c) and (2.6d) are replaced by:

x F ij + x F ji ≤ u ij y ij ∀[i, j] ∈ E, ∀F ∈ F x F ij + x F ji = 0 ∀F ∈ F, ∀[i, j] ∈ F (2.7a) (2.7b)
A feasible solution induced by y and x implies a flow of value |T | for each scenario F ∈ F. Then, if a given solution yields a strictly positive flow on both x F ij and x F ji for a given edge [i, j] and a given scenario F , there exists another flow at least as good as this one in which the flow verifies either x F ij = 0 or x F ji = 0 (see Remark 0.2.1 in Subsection 0.2.2 of the introduction).

Bilevel formulation

The bilevel formulation proposed here is particular in that the second level is a min max problem. It can be seen as a game with a defender and an attacker (corresponding respectively to the leader and the follower).

For each (i, j) ∈ A, we introduce a variable x ij which corresponds to the amount of flow that the defender chooses to route through the arc (i, j). The variable y is defined as in Subsection 2.2.1. We also introduce the binary variables b ij , ∀(i, j) ∈ A: b ij = 1 if and 2.2. FORMULATIONS only if the attacker chooses to delete the arc (i, j). Moreover, we assume without loss of generality that there is no arc entering r. Then, we can define the following polyhedron:

X (y, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ∑ i∈Γ -(j) x ij - ∑ k∈Γ + (j) x jk = 0 ∀j ∈ V \ {r, s} x ij ≤ u ij y ij ∀(i, j) ∈ A x ij ≤ u ij (1 -b ij ) ∀(i, j) ∈ A x ij ≥ 0 ∀(i, j) ∈ A ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ (2.8a) (2.8b) (2.8c)
This polyhedron X (y, b) corresponds to the set of possible flows on the subgraph of G induced by the arcs (i, j) ∈ A such that y ij = 1, provided they have not been deleted, i.e. b ij = 0. The polyhedron X (y, b) is defined by the flow conservation constraints, the capacity constraints and the constraints imposing a flow equal to 0 on any arc which is deleted. We also define the following polyhedron:

B = { b ∈ {0, 1} |A| | ∑ (i,j)∈A b ij ≤ k ; b ts = 0 ∀t ∈ T }
The polyhedron B defines the set of possible scenarios of arc failures (it ensures that no fictive arc can be deleted). We propose the following bilevel program:

(BILEV EL) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y∈{0,1} |A| ∑ (i,j)∈A c ij y ij s.t. f (y) ≥ |T | where f (y) = min b∈B max x∈X (y,b) ∑ j∈Γ + (r)
x rj

(2.9a) (2.9b)
where {(i, j) s.t. y ij = 1} defines the set of selected arcs. At the upper level, the defender selects the set of arcs to be added to the network, by choosing a value of y in {0, 1} A . The attacker then deletes some arcs by setting the variable b ∈ B in order to minimize the maximum flow that the defender will compute by setting the variable x in the flow polyhedron X (y, b). The aim of the defender is to ensure that this flow is at least equal to |T | (see Constraint (2.9a)).

FORMULATIONS

Consider the max problem in the lower level: at this stage, y and b are already fixed;

we refer to their values as ŷ and b respectively. The problem is a max-flow problem from r to s, with two sets of capacity constraints. In our problem, the flow must be integral since it corresponds to a number of terminals. However, it is well-known that the matrix of coefficients M in the arc-formulation of a max-flow is totally unimodular (see Subsection 0.2.2 in the introduction). Then, adding the second set of capacity constraints is equivalent to appending the identity matrix to M : the matrix remains totally unimodular and, since the capacities are integers, we ensure that the extreme points of the polyhedron defined by X (y, b) have integral coordinates. Thus, we can relax the integrality constraints on x.

In the max problem of the lower level (i.e. max x∈X (y,b)

∑ j∈Γ + (r)
x rj ), there always exists a feasible flow of value 0 and the problem is also trivially upper bounded by |T | (because of the cut-set with only the fictive arcs). Hence, the strong duality holds and we can introduce the dual of the lower level problem, where µ is the variable associated with Constraints (2.8a) while λ and γ are respectively associated with Constraints (2.8b) and

(2.8c). After a slight reformulation due to the addition of µ r and µ s , the dual problem can be written as follows (see Subsection 0.2.2 in the introduction):

(Φ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + ∑ (i,j)∈A u ij (1 -bij )γ ij s.t λ ij + γ ij -µ i + µ j ≥ 0 ∀(i, j) ∈ A µ r = 1 µ s = 0 λ, γ ∈ [0, 1] |A| , µ ∈ [0, 1] |V | (2.10a) (2.10b) (2.10c) (2.10d) Because (Φ) is the dual of the problem max x∈X (y,b) ∑ j∈Γ + (r)
x rj , we have that the matrix of constraints of (Φ) is totally unimodular (because it is the transpose of a totally unimodular matrix, see Property 0.2.1 in Subsection 0.2.2 in the introduction). Thus, the extreme points of (Φ) are integer. This problem is a special formulation of a min-cut problem: µ defines the two parts of the cut (sets of vertices i ∈ V such that either µ i = 0 or µ i = 1), an arc (i, j) is in the corresponding cut-set if µ i = 1 and µ j = 0. The variables 2.2. FORMULATIONS γ and λ define the cut-set of the corresponding cut: for each arc (i, j) in the cut-set, we have either λ ij = 1 or γ ij = 1. If an arc (i, j) is not in the cut-set, because we minimize the objective function with positive coefficients and µ j -µ i ≥ 0, we have γ ij = λ ij = 0 in an optimal solution. Moreover, because of the economic function and the positive capacities, we have that γ ij is equal to 1 for at least all arcs (i, j) in the cut-set with bij = ŷij = 1 (i.e., the arcs selected but deleted), while λ ij is equal to 1 for at least all arcs (i, j) in the cut-set with bij = ŷij = 0 (i.e., the arcs that are neither selected nor deleted). For other arcs in the cut-set, it does not matter which one is set to 1. We denote by D the polyhedron defined by dual Constraints (2.10a)- (2.10d).

Since the lower level can be reformulated as a minmin function by using the dual described above, it can then be rewritten as follows:

(LL) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + u ij (1 -b ij )γ ij s.t b ∈ B (λ, µ, γ) ∈ D
At this point, b is a variable, so the objective function is non-linear. We linearize the terms b ij γ ij in a classical way by introducing variables l ij = b ij γ ij where l ij verifies the set of constraints defined by L(b, γ):

L(b, γ) = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ l ∈ R |A| ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ l ij ≤ b ij ∀(i, j) ∈ A l ij ≤ γ ij ∀(i, j) ∈ A l ij ≥ γ ij -(1 -b ij ) ∀(i, j) ∈ A l ij ≥ 0 ∀(i, j) ∈ A ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭
The lower level can then be rewritten as follows:

(LL)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ,γ ∑ (i,j)∈A u ij ŷij λ ij + u ij γ ij -u ij l ij s.t b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ)

FORMULATIONS

We define the following function g:

g(y, λ, γ, l) = ∑ (i,j)∈A u ij y ij λ ij + u ij γ ij -u ij l ij
We can then rewrite the bilevel program as:

min y∈{0,1} |A| ∑ (i,j)∈A c ij y ij s.t f (y) ≥ |T | where f (y) = min b,λ,γ,µ,l g(y, λ, γ, l) s.t. b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ)
We can then consider the convex hull of the lower-level polyhedron defined by B, D and L(b, γ), and denote by H the set of its extreme points. One can notice that this convex hull does not depend on y (only g(•) does): the set of extreme points H remains the same for every y ∈ {0, 1} A . We denote by ( λh , γh , lh ) the respective values of (λ, γ, l) at the extreme point h ∈ H. We can then reformulate the bilevel formulation as a single-level one as follows:

min ∑ j∈Γ + (r) x rj is not defined because there are some values of b for which X (y, b) is empty. Furthermore the dualization of this polyhedron leads (LL) to be unbounded in this case.

∑ (i,j)∈A c ij y ij s.t. g(y, λh , γh , lh ) ≥ |T | ∀h ∈ H y ∈ {0, 1} |A| (BP) b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ) (2.11a) (2.11b) (2.11c) (2.11d) (2.
x ij ≤ u ij y ij and x ij ≤ u ij (1 -b ij ) could be replaced by x ij ≤ u ij (y ij -b ij )
A solution to this issue could be to add the set of constraints b ij ≤ y ij in the polyhedron B but it would lead to the presence of constraints which depend on y in the lower level.

Remark 2.2.2 In (BP), g(y, λ, γ, l) is non-linear because of the products y ij λ ij , but they can be linearized as it has been done for b ij γ ij above.

However, there is an exponential number of Constraints (2.11a). To tackle this issue, we use a constraints generation algorithm where we relax Constraints (2.11a) and use (LL) as the separation problem: while the optimum value of (LL) is smaller than |T | for the current solution ŷ (integer solution to (BP) with a subset of Constraints (2.11a)), we generate Constraints (2.11a) associated with the extreme point whose coordinates are the optimal values of (b, λ, γ, µ, l) in (LL). Property 2.2.1 Let ŷ1 and ŷ2 be two feasible solutions of (BP) such that ŷ1 ≥ ŷ2 , i.e., ŷ1 ij ≥ ŷ2 ij for each arc (i, j). If adding a constraint g(y, λa , γa , la ) ≥ |T | makes any solution with y = ŷ1 infeasible, then it also makes any solution with y = ŷ2 infeasible.

Proof: For any value ( λa , γa , la ) of (λ, γ, l), we have g(ŷ 1 , λa , γa , la ) ≥ g(ŷ 2 , λa , γa , la ) since ŷ1 ≥ ŷ2 (recall that u and λ are positive). Hence, if g(ŷ 1 , λa , γa , la )

≤ |T | -1, then g(ŷ 2 , λ a , γ a , l a ) ≤ |T | -1. □
To improve the cut added to (BP) to forbid the current non-feasible solution ŷ obtained by solving (LL) for each constraint generation, we search for an unfeasible solution y such that y ≥ ŷ in order to generate a stronger constraint, as explained in Property 2.2.1. To get these values, we first solve the following problem, and then we compute the new ŷ accordingly (as explained later). Given a starting solution ŷ, we propose to find a cut-set in the support network (i.e., in the initial digraph G) with a minimum number of arcs such that this cut-set is non-valid in the network induced by  (i.e. the arcs (i, j) such 2.2. FORMULATIONS that ŷij = 1), meaning that, if we remove k given arcs of the cut-set in Â, its remaining capacity is smaller than |T |. This can be modeled as follows:

min

∑ (i,j)∈A λ ij s.t ∑ (i,j)∈A u ij ŷij λ ij ≤ |T | -1 ∑ (i,j)∈A γ ij = k γ ts = 0 ∀t ∈ T (λ, µ, γ) ∈ D, µ ∈ {0, 1} |V | (2.12a) (2.12b) (2.12c)
The variables (λ, µ, γ) define a cut in the input graph since they belong to D (recall that D is the set of Constraints (2.10a)-(2.10d)): µ defines the two parts of the cut, while λ and γ define the arcs in the cut-set; in particular γ defines the arcs in the cut-set that are deleted. However, adding the other constraints makes the constraints matrix not unimodular anymore: thus, we have to set µ as a 0-1 variable. When µ is binary, there always exist an optimal solution with γ and λ binary: for an arc (i, j), if µ i = µ j or µ i = 0 and µ j = 1, we have that λ ij = γ ij = 0; if µ i = 1 and µ j = 0, we must have

λ ij + γ ij ≥ 1,
and because of the minimization of the objective function, there always exists an optimal solution such that exactly one between λ ij and γ ij is equal to 1. Constraint (2.12a) ensures that the cut-set selected is non-valid (i.e. has insufficient capacity). Constraint (2.12b) ensure that the number of deleted arcs is equal to k, while Constraints (2.12c) forbid the deletion of fictive arcs.

Then, the new values of the ŷij are computed as follows: we set ŷij to 1 for all (i, j)

with λ ij = γ ij = 0 and let the others to their current value. Indeed, we want to include as many arcs as possible in the solution, while ensuring that there exists a cut with capacity at most |T|-1: hence, any arc not associated with this cut can be included in the solution.

It implies that, for each arc (i, j), the new value of ŷij cannot be smaller than the old one, and, using Proposition 2.2.1, we generate a better constraint than the original one by computing the extreme points associated with this new value of ŷ.

RELATIONS BETWEEN THE FORMULATIONS

Undirected graphs

In order to obtain a formulation that works for the undirected case, we define for each edge [i, j] the variables y ij , b ij , x ij and x ji . The only modification appears in the polyhedron X (y, b), which can be modified as follows:

X (y, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x ∈ R |E| ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ∑ i∈Γ(j) x ij - ∑ k∈Γ(j)
x jk = 0 ∀j ∈ V \ {r, s}

x ij ≤ u ij y ij ∀[i, j] ∈ E x ji ≤ u ij y ij ∀[i, j] ∈ E x ij ≤ u ij (1 -b ij ) ∀[i, j] ∈ E x ji ≤ u ij (1 -b ij ) ∀[i, j] ∈ E x ij , x ji ≥ 0 ∀[i, j] ∈ E ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭
Again, since this polyhedron is associated with a maximum flow problem (when the values of y and b are fixed), we can always find a maximum flow where either x ij = 0 or

x ji = 0 for each edge [i, j] ∈ E. Once this polyhedron has been modified, one can use the method proposed for the directed case to solve the formulation.

Relations between the formulations 2.3.1 Relations between the bilevel and the cutset formulations

Let us formulate (SL) the second level of the bilevel formulation by replacing Constraints (2.8b) and Constraints (2.8c) by the constraint

x ij ≤ u ij (ŷ ij -b ij ) ∀(i, j) ∈ A (see the polyhedron X (y, b) in Remark 2.2.1 in Subsection 2.2.
3). We introduce the polyhedron B(y) = {b ∈ B | b ≤ y} to ensure that X (y, b) is non-empty for each possible value of b ∈ B(y), i.e. the second level is defined. We obtain:

(SL)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b∈ B(y) max x ∑ j∈Γ + (r) x rj s.t ∑ i∈Γ -(j)
x ij -

∑ k∈Γ + (j) x jk = 0 ∀j ∈ V \ {r, s} 0 ≤ x ij ≤ u ij (ŷ ij -b ij ) ∀(i, j) ∈ A (2.13a) (2.13b)

RELATIONS BETWEEN THE FORMULATIONS

We introduce a reformulation of (SL), moving the variable b to the objective function:

(RSL)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b∈ B(y) max x ∑ j∈Γ + (r)
x rj -

∑ (i,j)∈A b ij x ij s.t ∑ i∈Γ -(j)
x ij - Proof: Let f 1 ( b, x) (respectively f 2 ( b, x)) be the value of the objective function of (SL) (respectively (RSL)) when ( b, x) is a feasible solution of (SL) (respectively (RSL)).

∑ k∈Γ + (j) x jk = 0 ∀j ∈ V \ {r, s} 0 ≤ x ij ≤ u ij ŷij ∀(i, j) ∈ A (2.14a) (2.
Let x 1 be an optimal solution of the max problem of (SL) associated with b ′ ∈ B(y). We have that x 1 is obviously a feasible solution of (RSL). Furthermore, Constraints (2.13b)

imply that x 1 ij = 0 if b ′ ij = 1. Then b ′ ij x 1 ij = 0 for all arcs (i, j) and f 1 (b ′ , x 1 ) = f 2 (b ′ , x 1 ).
Let x 2 be an optimal solution of the max problem of (RSL) associated with b ′′ ∈ B(y).

If b ′′ ij x 2 ij = 0 for all arcs (i, j), x 2 is a feasible solution of the max problem of (SL) and f 2 (b ′′ , x 2 ) = f 1 (b ′′ , x 2 ). Otherwise there is at least one arc (u, v) such that b ′′ uv x 2 uv > 0 (thus x 2 is not feasible for the max problem of (SL)). Let x 3 be a new solution of (RSL) such that x 3 uv = 0, x 3 ij ≤ x 2 ij for each arc (i, j) ̸ = (u, v) and the value of the flow defined by x 3 is equal to the value of the flow defined by x 2 minus x 2 uv (i.e.

∑ j∈Γ + (r) x 3 rj = ∑ j∈Γ + (r) x 2 rj -x 2 uv ).
Such a flow always exists: we reduce by x 2 uv the value of the flow by reducing the amount of flow on one or several paths from r to s containing (u, v).

We have f 2 (b ′′ , x 3 ) = ∑ j∈Γ + (r) x 3 rj - ∑ (i,j)∈A b ′′ ij x 3 ij = ( ∑ j∈Γ + (r) x 2 rj -x 2 uv ) - ∑ (i,j)∈A b ij x 3 ij .
Because x 3 ≤ x 2 and x 3 uv = 0, we have that

∑ (i,j)∈A b ′′ ij x 2 ij ≥ ∑ (i,j)∈A b ′′ ij x 3 ij + x 2 uv and thus f 2 (b ′′ , x 3 ) ≥ ∑ j∈Γ + (r) x 2 rj -x 2 uv -( ∑ (i,j)∈A b ij x 2 ij -x 2 uv ) which leads to f 2 (b ′′ , x 3 ) ≥ f 2 (b ′′ , x 2 ): since x 2 is optimal we have f 2 (b ′′ , x 3 ) = f 2 (b ′′ , x 2
). We have found an optimal solution x 3

of the max problem of (RSL) with x 3 uv = 0 and x 3 ≤ x 2 . By using this method iteratively,

RELATIONS BETWEEN THE FORMULATIONS

we obtain a solution x h with

∑ (i,j)∈A b ′′ ij x h ij = 0.
Thus, x h is optimal for (RSL) and feasible for (SL) and

f 2 (b ′′ , x 2 ) = f 2 (b ′′ , x h ) = f 1 (b ′′ , x h ).
The optimal values of (SL) and (RSL) are then the same considering we can transform an optimal solution for (SL) to a solution for (RSL) of same value and vice versa. □

In an optimal solution of (RSL), the defender will then route no flow through arcs which had been deleted by the attacker because it would reduce the value of his objective function. We can also replace the constraint b ∈ B(y) by b ∈ B in (RSL) (i.e. deleting the constraint b ≤ y) since the polyhedron of the max problem is defined for each b ∈ B. This does not affect the optimal value of (RSL) since, for an arc (i, j), x ij = 0 if y ij = 0 and thus b ij x ij = 0 no matter the value of b ij .

Property 2.3.1 can also be seen as a consequence of a Wood's result [START_REF] Wood | Bilevel network interdiction models: Formulations and solutions[END_REF]].

Wood considers the following generic bilevel network interdiction model:

(BN I1) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min z∈Z max w c ⊤ w s.t Aw ≤ a 0 ≤ w ≤ U (1 -z)
where Z = {z ∈ {0, 1} n | Hz ≤ h} is the polyhedron of the attacker variable z (for a facility f , z f = 1 if the facility f is attacked, 0 otherwise). The defender operates the network to maximize his objective function by setting the variable w, considering the damages made by the attacker (if z f = 1, there cannot be any activity on the facility f , i.e. w f = 0 because of the constraint 0 ≤ w ≤ U (1 -z)). We have U = diag(u) where u is the upper bound vector of w (for example a capacity).

Let r f be an upper bound on the optimal dual variable for the constraint

w f ≤ u f (1 - z k ) in (BN I1
). We introduce r = (r 1 ...r n ) ⊤ and R = diag(r). Wood defines the following formulation:

2.3. RELATIONS BETWEEN THE FORMULATIONS (BN I2) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min z∈Z max w (c ⊤ -z ⊤ R)w s.t Aw ≤ a 0 ≤ w ≤ u
In Wood [2010, Proposition 1], Wood shows that (BN I1) and (BN I2) are equivalent in the sense that their optimal values are equal and z * is an optimal solution for (BN I2)

if and only if it is an optimal solution for (BN I1). Using this proposition on (SL), we re-obtain the formulation (RSL) (R corresponds to the identity matrix in our case since dual variables can be bounded by 1 similarly to Subsection 2.2.3).

Again, at this point, the variable ŷ and b are fixed. The defender subproblem (RSL)

can then be dualized in this way:

min λ,µ ∑ (i,j)∈A u ij ŷij λ ij s.t λ ij -µ i + µ j ≥ -bij ∀(i, j) ∈ A µ r = 1 µ s = 0 λ ∈ [0, 1] |A| , µ ∈ [0, 1] |V | (2.15a) (2.15b) (2.15c) (2.15d)
The lower level can be reformulated as a minmin function by using the dual described above, thus it can be rewritten as follows:

(DRSL)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ ∑ (i,j)∈A u ij ŷij λ ij s.t b ∈ B λ ij + b ij -µ i + µ j ≥ 0 ∀(i, j) ∈ A µ r = 1 µ s = 0 λ ∈ [0, 1] |A| , µ ∈ [0, 1] |V | (2.16a) (2.16b) (2.16c) (2.16d) (2.16e)
We can then rewrite the bilevel program as:

2.3. RELATIONS BETWEEN THE FORMULATIONS min y∈{0,1} |A| ∑ (i,j)∈A c ij y ij s.t f (y) ≥ |T | where f (y) = min (b,λ,µ)∈D ∑ (i,j)∈A u ij y ij λ ij
where D is the polyhedron defined by Constraints (2.16a-2.16e).

One can notice that (DRSL) is strictly equivalent to the separation problem of the cutset formulation (2.4a-2.4e). Let us rewrite Constraint (2.3) from the cut-set formulation:

∑ (i,j)∈S\C u ij y ij ≥ |T | ∀S ∈ S, ∀C ∈ C S k
where S is the set of r-s cutsets except the one implying only fictive arcs and C S k is the set of subsets of S of non-fictive arcs of size k, for any set S ∈ S. We can see that using the method generating the inequalities associated with the extreme points of the convex hull of (DRSL) proposed in Subsection 2.2.3 generates the same inequalities as (2.3), since the extreme points of (DRSL) represented by the values ( b, λ, μ), which are integer because of the total unimodularity of the matrix of constraints of (DRSL), will represent cuts on the graph given by μ: a vertex v is in the same part as the root if µ v = 1 and in the same part as the sink if µ v = 0. The residual cut-set S \ C is represented by the arcs (i, j) such that λij = 1, the deleted arcs C in the cut-set are represented by the arcs (i, j) such that bij = 1.

It is then clear that the bilevel formulation collapses with the cut-set formulation, as stated in Theorem 2.3.1.

Theorem 2.3.1

The optimal values of the continuous relaxations of (BILEV EL) and (CU T ) are equal.

Thus, we will only give the numerical results obtained for the cut-set and the flow formulations.

Relations between the flow and the cutset formulations

Let us introduce the continuous relaxation of the cutset formulation:

(RCF ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y ∑ (i,j)∈A c ij y ij s.t ∑ (i,j)∈S\C u ij y ij ≥ |T | ∀S ∈ S, ∀C ∈ C S k 0 ≤ y ij ≤ 1 ∀(i, j) ∈ A
We remind that S is the set of cut-sets associated with the r -s cuts [V \ V S , V S ] with

V S ⊂ V , r ∈ V \ V S , s ∈ V S
and V S ̸ = {s} and that for any S ∈ S, C S k is the set of subsets of non-fictive arcs of S of size k.

We also introduce the continuous relaxation of the flow formulation:

(RF F ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min x,y ∑ (i,j)∈A c ij y ij s.t. ∑ i∈Γ -(j) x F ij - ∑ k∈Γ + (j) x F jk = 0 ∀j ∈ V \ {r, s}, ∀F ∈ F ∑ t∈Γ -(s) x F ts = |T | ∀F ∈ F x F ij ≤ u ij y ij ∀(i, j) ∈ A, ∀F ∈ F x F ij = 0 ∀F ∈ F, ∀(i, j) ∈ F x ∈ R |A|×|F | + , y ∈ [0, 1] |A|
Let us call (y 1 , x 1 ) a feasible solution for (RF F ). Setting y = y 1 for (RCF ) would give a solution with the same value. Let us check that such a solution is feasible for (RCF ).

Since (y 1 , x 1 ) is feasible for (RF F ), there exists a flow of value |T | for each scenario of breakdown of k arcs, considering the capacity u ij y 1 ij on each arc (i, j), except obviously the arcs which are attacked in this scenario which have a capacity equal to 0. Let us assume that y 1 is not a feasible solution for (RCF ). Then there is at least one constraint of type

∑ (i,j)∈S\C u ij y 1 ij ≥ |T | which is violated for some S ∈ S and C ∈ C s k . If such a constraint
is violated, it means that there is a r -s cut-set for which the capacity is lower than |T | if we delete k arcs (again the capacity of each arc (i, j) here is u ij y 1 ij ). Then, the scenario of breakdown F ∈ F in which those k arcs are deleted would not admit a feasible flow of value |T |: a contradiction. So y 1 is a feasible solution for (RCF ) with the same value 2.4. ADDITION OF PROTECTED ARCS than (y 1 , x 1 ) for (RF F ). Now let us call y 2 a feasible solution for (RCF ). Setting y = y 2 for (RF F ) would give a solution with the same value. Assume there does not exist any x 2 such that (y 2 , x 2 ) is a feasible solution for (RCC). It means that there exists at least a scenario of breakdown F ∈ F such that there is no feasible flow of value |T | on the residual network (where we delete the arcs in F ) with capacities equal to u ij y 2 ij for each arc (i, j). As before, this is impossible since this would involve a residual r -s cut-set with a capacity lower than |T |. So there always exists at least one x 2 such that (y 2 , x 2 ) is a feasible solution for (RF F ).

We can then transform any solution of (RF F ) in a solution of same value in (RCF ) and vice versa and deduce Theorem 2.3.2.

Theorem 2.3.2 The optimal values of the continuous relaxations of the flow formulation

(RF F ) and the cut-set formulation (RCF ) are equal.

Addition of protected arcs

Let us now define another version of the problem, where we add the possibility of protecting k ′ arcs. In this version, in addition to A ′ , we also select a subset A ′ p ⊂ A ′ with |A ′ p | ≤ k ′ ; those arcs are called protected arcs and cannot be deleted by the attacker. The corresponding problem is called Capacitated Protected Rooted k-Edge Connected Steiner Network problem (CPRkECSN). In the wind farm application, protecting arcs can be seen as doubling a set of cables under a given budget for example, or protecting cables from a difficult environment (like extreme cold).

Remark 2.4.1 With the addition of protected arcs, Property 2.1.1 in Section 2.1 does

not hold anymore: if some arcs are protected, a feasible solution does not necessarily imply that there are k + 1 arc-disjoint paths between the root and each terminal t. For example, k + 1 paths which are pairwise arc-disjoint except for the fact that they share a common 2.4. ADDITION OF PROTECTED ARCS arc (u, v) can be sufficient to ensure that the terminal t can be reached from the root even after any k arc-deletions if the arc (u, v) is protected and capacities are sufficient. Hence, Remark 2.1.1 can also be ignored.

For each non-fictive arc (i, j) ∈ A I , we define the variable p ij as a binary variable equal to 1 if the arc (i, j) is protected, and to 0 otherwise. We also define the following polyhedron:

P = { p ∈ {0, 1} |A I | | ∑ (i,j)∈A I p ij ≤ k ′ ; p ij ≤ y ij ∀(i, j) ∈ A I }
This set ensures that there are at most k ′ protected arcs, and that we cannot protect arcs which are not selected in the final network. In the following, we propose small modifications to each one of the previous formulations in order to include the possibility of protecting arcs.

Cut-set formulation

In order to include the possibility of protecting arcs to the cut-set formulation proposed in Subsection 2.2.1, Constraints (2.3) can be replaced by the following ones:

∑ (i,j)∈S u ij y ij - ∑ (i,j)∈C u ij (y ij -p ij ) ≥ |T | ∀S ∈ S, ∀C ∈ C S k (2.17)
Constraints (2.17) ensure that the capacity of each cut-set minus the capacity of k unprotected arcs of this cut-set is always larger than |T |. We also add to the cut-set formulation the constraint p ∈ P .

We solve the resulting MIP using the same constraints generation algorithm as in Subsection 2.2.1. The separation problem is slightly modified to take into account the fact that the capacity of the protected arcs cannot be removed to compute the residual capacity of the cut-set. For small values of k, for each combinations of k selected but non-protected arcs, we compute the min-cut (in Subsection 2.2.1, we take into account all selected arcs). Considering the MIP CU T -SEP (see Subsection 2.2.1) used to solve the 2.4. ADDITION OF PROTECTED ARCS subproblem, we have to modify the objective function to find a cut-set that is violating some Constraint 2.17, which results in:

(CU T -SEP -P ROT ) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min s,b,v ∑ (i,j)∈ Â(u ij s ij + u ij pij b ij ) s.t s ij + b ij -v i + v j ≥ 0 ∀(i, j) ∈ Â v r = 1 v s = 0 ∑ (i,j)∈ Â b ij ≤ k ∑ t∈T b ts = 0 s ij , b ij ∈ {0, 1} ∀(i, j) ∈ Â, v ∈ {0, 1} |V | (2.18a) (2.18b) (2.18c) (2.18d) (2.18e) (2.18f)
where p corresponds to the current value of p. We remind that v defines the partition of the vertex set while s and b define the arcs of the cut-set, in particular b defines all the arcs of the cut-set which are deleted. The objective value is equal to the sum of the capacity of the arcs of the cut-set which are not deleted plus the capacity of the arcs which are deleted but were protected. There always exists an optimal solution where b ij pij = 0 for each arc (i, j): if there is some pij b ij > 0, we can set s ij = 1 and b ij = 0 which results in a solution with the same objective value which still satisfies all the constraints. Thus, we can add the constraints

b ij ≤ 1 -pij ∀(i, j) ∈ Â (2.19)
and set the objective function to

min s,b,v ∑ (i,j)∈ Â u ij s ij
Thus, protected arcs cannot be deleted.

Remark 2.4.2 When arcs can be protected, the case of uniform capacities equal to U does not admit the reformulation (2.5) anymore. For example, for a cut-set S ∈ S, if all arcs of S are protected, we must just ensure that their capacity is at least equal to |T |, whereas if no arc is protected we must ensure that

∑ (i,j)∈S u ij y ij -kU is at least equal to |T |.

Equivalence between cut-set and bilevel formulations in the protected case

The bilevel formulation introduced in Subsection 2.2.3 can be adapted to the protected case as follows:

(BIL -P ROT )

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y∈{0,1} |A| ∑ (i,j)∈A c ij y ij s.t. f (y) ≥ |T | where f (y) = min b∈B(p) max x∈X (y,b) ∑ j∈Γ + (r)
x rj

(2.20a) (2.20b) where b ∈ B(p) with

B(p) = { b ∈ {0, 1} |A| | ∑ (i,j)∈A b ij ≤ k ; ∑ t∈T b ts = 0 ; b ij ≤ 1 -p ij ∀(i, j) ∈ A }
forbids the attacker to delete some protected arcs.

The reformulation of the second level results in:

(RSL -Prot) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b∈ B(p) max x ∑ j∈Γ + (r)
x rj -

∑ (i,j)∈A b ij x ij s.t ∑ i∈Γ -(j)
x ij -

∑ k∈Γ + (j) x jk = 0 ∀j ∈ V \ {r, s} 0 ≤ x ij ≤ u ij ŷij ∀(i, j) ∈ A (2.21a) (2.21b)
This leads to the dual reformulated second level problem:

(DRSL -Prot) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min b,λ,µ ∑ (i,j)∈A u ij ŷij λ ij s.t λ ij + b ij -µ i + µ j ≥ 0 ∀(i, j) ∈ A µ r = 1 µ s = 0 ∑ (i,j)∈A b ij ≤ k ∑ t∈T b ts = 0 b ij ≤ 1 -pij ∀(i, j) ∈ A λ ∈ [0, 1] |A| , µ ∈ [0, 1] |V | , b ∈ {0, 1} |A| (2.22a) (2.22b) (2.22c) (2.22d) (2.22e) (2.22f) (2.22g)

VALID AND STRENGTHENING INEQUALITIES

which is equivalent to (CU T -SEP -P ROT ) in Subsection 2.4.1. Similarly to Subsection 2.3.1, the two formulations are equivalent as in the unprotected case.

Flow formulation

In the flow formulation, in addition to the constraint p ∈ P , we can replace Constraints

(2.6d) by the following ones:

x F ij ≤ u ij p ij ∀F ∈ F, ∀(i, j) ∈ F (2.23)
Those constraints ensure that in a scenario F where an arc (i, j) ∈ F , we can route some flow through this arc (i, j) only if this arc is protected. Again, we can use the same columns-and-constraints generation algorithm as in Subsection 2.2.2, in order to find the most vital arcs in the separation problem among the non-fictive and non-protected arcs (we consider only combinations of selected but non-protected arcs when computing the set of maximum flows).

Valid and strengthening inequalities

In this section, we propose some valid or strengthening inequalities for both formulations to enhance the quality of the lower bound obtained by solving the continuous relaxation. We first consider the case where we are not allowed to protect some arcs of the network. Secondly, we propose modifications of those inequalities to take the possibility of protecting arcs into account.

Case without the possibility of protecting arcs

Inequalities (2.24a) ensure that there are at least k + 1 arcs entering each terminal.

Indeed, if there are less than k + 1 arcs entering it, then it is possible to delete all of them and thus to prevent one unit of flow from reaching the sink. Inequality (2.24b) states the

VALID AND STRENGTHENING INEQUALITIES

same constraint for the arcs leaving the root.

∑ (i,t)∈A y it ≥ k + 1 ∀t ∈ T ∑ (r,i)∈A y ri ≥ k + 1 (2.24a) (2.24b)
Both Inequalities (2.24a) and (2.24b) are valid and cut some non-integer solutions. In Figure 2.2, we have T = {t 1 } and let u i be the capacity of a i for i = 1, .., 5 and y i be the variable associated with the selection of a i . The constraints associated with this graph for the cut-set formulation with k = 1 are u 1 y 1 ≥ 1, u 2 y 2 ≥ 1, u 3 y 3 ≥ 1, u 4 y 4 ≥ 1 and y 5 = 1. If we set u i = 2 for all i = 1, .., 4 (u 5 = 1 because a 5 is a fictive arc), we have that the solution in which y 1 = y 2 = y 3 = y 4 = 0.5 and y 5 = 1 is optimal for the continuous relaxation since we consider positive costs in the objective function. Inequalities (2.24a) are then violated and impose that y 3 + y 4 ≥ 2 (i.e. y 3 = y 4 = 1). Similarly, Inequalities

(2.24b) impose that y 1 + y 2 ≥ 2 (i.e. y 1 = y 2 = 1). In this case, the addition of both inequalities results in the cut of non-integer solutions (here, it even results in an optimal value of the integer problem equal to the optimal value of the continuous relaxation). Inequalities (2.25a) state that, for each Steiner vertex j, if an arc entering j is selected, then at least one arc leaving j must be selected, since all arc costs are assumed to be positive. Inequalities (2.25b) state the same for arcs leaving a Steiner vertex j. Notice that these inequalities cut some integer but non-optimal solutions.

y ij ≤ ∑ k∈Γ + (j) y jk ∀j ∈ V \ {T ∪ {r}}, ∀i ∈ Γ -(j) y jk ≤ ∑ i∈Γ -(j) y ij ∀j ∈ V \ {T ∪ {r}}, ∀k ∈ Γ + (j) (2.25a) (2.25b)

Case with the possibility of protecting arcs

The two families of Inequalities (2.24a) and (2.24b) are only true for the case without protection (k ′ = 0). Since one arc may be sufficient to ensure that one of the terminals is not isolated if it is protected, we can replace Inequalities (2.24a)

y it ≥ 1 + (k(1 - ∑ (i,t)∈A p it )) ∀t ∈ T ∑ (i,t)∈A y it ≥ 1 ∀t ∈ T ∑ (r,i)∈A y ri ≥ 1 + (k(1 - ∑ (r,i)∈A p ri )) ∑ (r,i)∈A y ri ≥ 1 (2.26a) (2.26b) (2.26c) (2.26d)
Inequalities (2.27) state that at least one arc entering a terminal t must be protected if there are less than k + 1 arcs entering t.

∑ (i,t)∈A p it ≥ 1 ∀t ∈ T with |Γ -(t)| ≤ k (2.27)
Inequalities (2.25a) and (2.25b) are still valid inequalities for the case with the possibility of protecting arcs.

Results analysis

In this section, we present the results of the tests for the formulations proposed previously. All experiments were performed on a computer with a 2.40GHz Intel(R) Core(TM) i7-5500U CPU and a 16GB RAM, using the solver CPLEX version 12.6.1, interfaced with Julia 0.6.0. We used in particular the package JuMP, a tool allowing mathematical modeling. For each test, the algorithm has been stopped after 3000 seconds if it has not terminated yet. The graph associated with each instance is parse, corresponding to the wind-farm application where graphs are not dense. Also, the formulations are very dependent on the number of arcs and graphs which are too dense would be too difficult to solve (for similar reasons, the number of vertices is bounded by 100).

The arc capacities are high enough to ensure that there is at least one feasible solution to our problem, but low enough to keep the problem difficult enough to solve. More precisely, the capacities are chosen randomly among four values: 0.8|T |, 0.6|T | and, except for the 2.6. RESULTS ANALYSIS edges with endpoints at distance 1 or 2 from the root, 0.4|T | and 0.2|T |. Furthermore, the cost of an arc depends on both its length and its capacity, and hence is not necessarily integral.

Table 2.2 presents the results for the cutset and flow formulations for one possible arc deletion and no protection allowed (i.e. k = 1 and k ′ = 0) on instances with non-uniform capacities. The column I gives the number of the instance on which the formulation is tested, the column gap LR gives the gap between the optimal value of the initial continuous relaxation with the valid inequalities and the optimal integer value (please remind that the relaxations of the flow and cutset formulations are equal, see Theorem 2.3.2). For each formulations, the column gap f gives the final gap between the best lower bound best LB and the best integer solution found best I (if the gap is equal to 0, we have found an optimal solution, otherwise we give the gap obtained after 3000 seconds of computation): formally we have that gap f = (best I -best LB )/best I ; the column time gives the time in seconds needed to find an optimal solution or 3000 if the algorithm has not terminated yet; the column it gives the number of iterations performed by the algorithm (i.e. the number of times the algorithm of constraints generation is executed); the column nodes gives the number of nodes explored in the branch-and-cut.

In Table 2.2, we can observe that both formulations manage to find an optimal solution to the problem within 3000 seconds for instances with a number of vertices smaller than or equal to 45, except for two instances for the flow formulation. However, the cutset formulation has a better solving time for almost all instances, although it performs more iterations of constraints generation and has a higher number of nodes explored in the branch-and-cut. This can be explained by the fact that although the number of constraints that can be generated in the cutset formulation is importantly higher than the family of constraints that can be generated in the flow formulation for k = 1 (whose number is bounded by |E|), at each constraint generation in the flow formulation, we add at least |E| variables to the formulation. On instances having 50 to 100 vertices, the cutset formulation allows to find a feasible solution which is often optimal or has a value close to 2.2. For some instances, the instance does not admit any feasible solution for k = 2 and k ′ = 0, thus we remove from the table those instances (the formulations determine when no solution exists within a few seconds for this set of instances). Again, the cutset formulation is way more efficient than the flow formulation. The flow formulation still presents a smaller number of constraints generation iterations but the difference with the number of iterations of the cutset formulation is less important than for k = 1, due to the fact that we now may have to generate up to

( |E| 2 )
constraints, whereas the number of iterations for the cutset formulations is only slightly higher for k = 2 than for k = 1.

In Table 2.3, the cutset formulation manages to find an optimal solution for most of the instances of at most 70 vertices, and does not appear to be as sensitive to the value of k as the flow formulation. For instances with 80 vertices and more, the cutset formulation manages to find a feasible solution which is optimal or has a value reasonably close to the optimal one. The algorithm associated with the cutset formulation finds the optimal solution for 22 instances out of 30 tested. For the other instances, the mean final gap is equal to 0.9.

Table 2.4 presents the results of the cutset and flow formulations for k = 3 and k ′ = 0 on instances with non-uniform capacities. The columns are defined similarly to the previous tables. Again, some instances do not admit any feasible solution for k = 3 and k ′ = 0, thus to 0, we have found an optimal solution, otherwise we give the gap obtained after 3000 seconds of computation); the column time gives the mean solving time to find an optimal solution or 3000 if the algorithm has not terminated yet for the data set; the column it gives the mean number of iterations performed by the algorithm (i.e. the number of times the algorithm of constraints generation is executed) for the data set; the column n gives the mean number of nodes explored in the branch-and-cut for the data set.

One can see that the cutset formulation is also more efficient with the addition of the possibility of protecting arcs. The solving time is higher in the case with k ′ > 0 than in the case with k ′ = 0 and it increases as well as the gaps and the number of iterations and nodes when k ′ becomes bigger. It appears that the flow formulation is slightly less impacted by the variation of k ′ .

Table 2.6 presents the results of the cutset and flow formulations for k = 2 and k ′ ∈ {1, 2, 3} on instances with non-uniform capacities; the columns are similar to the ones in Table 2.5. The flow formulation is logically still importantly slower when k increases in the protected case, and the mean number of iterations is around the double of the one for k = 1. Again, the cutset formulation appears to be less impacted by the increase of k in the protected case: the gaps are equivalent, the solving times appear to be even better for some sets of instances (sets 41-50 and 51-58), and the number of iterations does not increase as much as the ones of the flow formulation. The results are impressive in comparison to the case with non-uniform capacities. The solving times are much smaller, as well as the mean number of nodes and the mean number of iterations for both Regular-Cutset and Uniform-Cutset formulations. The Uniform-Cutset formulation appears to be more efficient, which appears to be logical since the number of constraints of the formulation is highly reduced and the number of variables remains the same. The number of iterations is always smaller than the one of the Regular-Cutset formulation and the number of nodes is often smaller than the one of the regular formulation too.

Table 2.9 presents the results obtained with the Regular-Cutset and Uniform-Cutset formulations for k = 2 and k ′ = 0 on instances with uniform capacities. Columns are defined as in Table 2.8. For k = 2, the uniform formulation appears to be way more efficient than the regular one. The mean solving time and number of iterations and nodes have only slightly increased with the incrementation of k for the uniform formulation (the mean solving time for each instance is bounded by 70 seconds) whereas it has consequently increased for the regular one (the mean solving time is around 2678 seconds for Instance 51 for example). formulations for k = 3 and k ′ = 0 on instances with uniform capacities. Columns are defined as in Tables 2.8 and 2.9. Again, the uniform formulation appears to be a con- sequent upgrade of the regular one, and the solving times are really smaller than in the non-uniform case.

We also compute the results obtained by both formulations, without the addition of the valid inequalities proposed in Subsection 2.5, on a subset of instances with k ∈ {1, 2, 3}, k ′ = 0, and non-uniform capacities. Let ∆ C time (respectively ∆ F time ) be the mean augmentation of the solving time when these valid inequalities are removed from the cut-set (respectively flow) formulation. On the test instances, ∆ C time is equal to 3.24 (meaning that the solving time is multiplied by 3.24 on average without the valid inequalities), while ∆ F time is equal to 10.78. Hence, adding these valid inequalities has a huge impact on the solving time, especially on the flow formulation. Furthermore, let ∆ CR be the mean augmentation of the optimal value of the continuous relaxation when these valid inequalities are added to the formulation. On the test instances, ∆ CR is equal to 1.28 (meaning that the optimal value of the continuous relaxation is multiplied by 1.28 on average with these valid inequalities). The optimal value of the continuous relaxation is then consequently increased when we add these valid inequalities. (d) correspond to the case where k ′ is equal to 1, 2 and 3, respectively. This figure shows that designing a network resilient to even a small number of arc-failures can be costly (the cost increases greatly with the value of k). However, on subfigure (d), we can see that, by protecting a sufficiently large but still small subset of arcs on the test instances, one can obtain networks that are resilient to 1 or 2 arc deletions while maintaining a cost close to the optimal value of the case with no arc failures.

TESTING SURVIVABILITY

and comparisons with the exact algorithm introduced in Chapter 2 are presented in Section 3.4.

Testing survivability

Given a subset A ′ of the original arc set A, we present in this section a method to test whether G ′ = (V, A ′ ) is k-survivable, based on a method proposed in [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF]].

Every arc a = (i, j) ∈ A ′ has an associated upper bound u a = u ij (called capacity) on the amount of flow that can traverse it, while the lower bound l a = l ij is equal to zero since there is no imposed flow on any arc of G ′ (we introduce lower bounds here because they will be used later for other arcs).

The first step of the procedure consists in determining a subset of arcs S in the complete graph associated with V such that S corresponds to a tree rooted at r spanning all terminals of T and S does not break the planarity of the input graph G ′ (i.e. if we add the arcs of S to G ′ , the graph G ′′ = (V, A ′ ∪ S) is still planar), which is an easy task.

Note that such a tree necessarily exists since r is a root and we do not forbid the graph G ′′ = (V, A ′ ∪ S) to be a multigraph (i.e. we can select in S arcs from A ′ ): an easy solution to find S is then to compute a tree using arcs of A ′ (and this is what we will do).

For every vertex v in S, let n v be the number of terminals in the subtree rooted at v.

For each arc (i, j) in S, we add the reverse arc (j, i) in G ′ and set l ji = u ji = n j (there is no issue if (j, i) is already in A ′ since the resulting graph can be a multigraph). We denote by A R the set of arcs added to G ′ and by G′ the resulting graph. An example is depicted in Figure 3.1. The left graph G ′ has two terminals t 1 and t 2 . The directed tree S with arc set {(r, u), (u, t 1 ), (u, v), (v, t 2 )} induces the graph G′ on the right, the arcs in A R being represented by bold lines. Since

n r = n u = 2 while n v = n t 1 = n t 2 = 1, all arcs (j, i) in A R have l ji = u ji = 1, except the arc (u, r) for which l ur = u ur = 2.
The circulation problem is a generalization of the network flow problem where flow 3.2. TESTING SURVIVABILITY

t 1 t 2 r v u t 1 t 2 r v u [2,2] [1,1] [1,1] [1,1] Figure 3.1: Construction of G′ from G ′ .
conservation is required for all vertices (i.e. there are no source and sink). It is easy to observe that the original graph G ′ has a feasible flow routing a unit of flow from r to each terminal if and only if the extended graph G′ has a feasible circulation: the flow sent from the root to the terminals travels back to r using the arcs in A R .

The problem of determining whether G ′ is k-survivable was shown to be NP-complete in the general case [START_REF] Wood | Deterministic network interdiction[END_REF]], but can be solved in polynomial time if the graph G ′ + t obtained from G ′ by adding a sink t to which all terminals are linked is planar [START_REF] Phillips | The network inhibition problem[END_REF]]. Since the addition of a sink to a planar graph G ′ does not necessarily preserves planarity, Zenklusen [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF]] has shown how to solve the problem in polynomial time when G ′ (and not necessarily G ′ + t) is planar. His procedure is described here below.

Notice first that if G ′ is planar, then G′ is also planar. We can therefore consider its dual. By convention (see [Lawler 2001] for more details), the dual of a directed planar graph is obtained by creating a vertex for each face of the original graph, and by connecting two vertices by an arc if they correspond to faces in the original graph sharing an arc. Every dual arc is oriented so that it corresponds to a 90 • anticlockwise turn from the corresponding primal arc. As proposed by Zenklusen [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF]], we consider here an extended dual graph that contains not only the standard dual arcs, but also the arcs with the opposite direction. More precisely, we build a graph D G′ from G′ as follows. We first create a vertex in D G′ for every face in G′ . Then, for every arc (i, j) in G′ , we 3.2. TESTING SURVIVABILITY consider the two faces F 1 and F 2 that (i, j) separates (see Remark 3.2.1), where F 1 is the face below (i, j) when (i, j) is drawn horizontally with an arrow going from left to right.

We create an arc (F 1 , F 2 ) of length u ij and an arc (F 2 , F 1 ) of length -l ij in D G′ . Note that (F 1 , F 2 ) is the standard dual arc associated with (i, j), while (F 2 , F 1 ) is the opposite one.

We also denote by a d ij the standard dual arc (F 1 , F 2 ) in order to distinguish it from its opposite. Note that the arc (F 2 , F 1 ) has length 0 if (i, j) ∈ A ′ (since there is no imposed flow on any arc of G ′ ), while its length is -n j if (i, j) ∈ A R .

The construction of D

G′ from G′ is illustrated in Figure 3.2. The general arc creation procedure appears on the left, while the dual graph associated with the graph G′ of Figure 3.1 is drawn on the right with dashed lines. To simplify the drawing, arcs with arrows on both sides represent two oppositely directed arcs. If we delete (i, j), G ′ is then non-connected: we call G 1 (resp. G 2 ) the component with the vertex i (resp. j). Since the arc is from i to j, we have that r is in G 1 , otherwise the arc (i, j) is useless. If there is at least one terminal t in G 2 , then there does not exist a path from r to t after the deletion of (i, j) and hence G ′ is not k-survivable. Otherwise, the arc (i, j) is useless because G 2 can be disconnected from the graph without impacting the feasibility of the solution. Hence, we consider that there are no bridges in G ′ .

t 1 t 2 r v u c a e d g h f b [l ij ,u ij ] face F 2 i j face F 1 vertex associated with F 2 vertex associated with F 1 u ij -l ij

TESTING SURVIVABILITY

Zenklusen [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF]] has shown that there exists a feasible circulation in G′ if and only if there is no negative circuit in D G′ . Indeed, there is a correspondence between the circuits in D G′ and the cutsets in G′ . In a circuit of D G′ , the total length of the standard dual arcs corresponds to the available capacity, while the absolute value of the total length of the other arcs corresponds to the demand. A circuit of negative total length means that the demand cannot be satisfied. For example, consider the circuit (f, d, h, g, f ) in the graph D G′ of Figure 3.2: the standard dual arcs (f, d) and (h, g) give a total capacity u ut 1 + u t 2 t 1 , while the other arcs (d, h) and (g, f ) induce a demand of 1 unit (since

|l dh + l gf | = | -1 + 0| = 1)
, which means that u ut 1 + u t 2 t 1 must be at least equal to 1 to satisfy the demand of terminal t 1 .

The above construction shows how to determine if G ′ = (V, A ′ ) has a feasible flow, which is equivalent to deciding whether G′ has a feasible circulation. By definition, G ′ is k-survivable if and only if there is no subgraph G ′′ of G ′ , obtained by removing at most k arcs of A ′ , so that G′′ has no feasible circulation. Every arc removal is equivalent to paying one unit of a budget of k units, and we therefore try to find a subgraph G ′′ of G ′ so that G′′ has no feasible circulation, without exceeding the budget. Zenklusen [START_REF] Zenklusen | Network flow interdiction on planar graphs[END_REF] (who considers more general budget constraints) shows how this can be done by solving a multi-objective shortest path problem. In our simpler case, we propose to consider a graph (k + 1)D G′ that is built as follows. We make k + 1 copies of D G′ , and for every arc (i, j) in A ′ , we consider its standard dual arc a d ij = (x, y) in D G′ , and add links of length 0 from the s-th copy of x to the (s + 1)-th copy of y (s = 1, . . . , k). Note that if a vertex v is not the tail of any standard dual arc (v, w) in D G′ , then each of its neighbors in D G′ is the tail of at least one standard dual arc (since if (v, w) is not a standard arc, then (w, v) is). The resulting graph is denoted by (k + 1)D

G′ . An example for k = 1 and the graph D G′ of Figure 3.2 is given in Figure 3.3. Since A ′ contains seven arcs, there are seven arcs linking the first to the second copy of D G′ .

We now prove that it is possible to test the k-survivability of G ′ by solving a series of shortest path problems in (k + 1)D G′ . G′ for the graph G′ of Figure 3.1 .

TESTING SURVIVABILITY

Theorem 3.2.1 A graph G ′ = (V, A ′ ) is k-survivable if

and only if all shortest paths

linking a first to a (k + 1)-th copy of a vertex in (k + 1)D G′ have a non-negative length.

Proof: Assume G ′ = (V, A ′ ) is not k-survivable.
As explained previously, this means that there is a circuit C in D G′ and a subset A C of its arc set such that |A C | ≤ k, all arcs in A C are standard dual arcs, and the total length L of the other arcs on C is strictly negative (because deleting an arc in the primal graph corresponds to contracting the two vertices associated in the dual graph). Let v be a vertex on C which is the tail of at least one standard dual arc (not necessarily on C) in D G′ (note that there always exists such v since we showed that if v is not the tail of any standard dual arcs then each of its neighbors is the tail of at least one standard dual arc). Consider the path P in (k + 1)D

G′ that links the first to the (|A C | + 1)-th copy of v, and uses arcs (x, y) that link consecutive copies of D

G′ whenever an arc (x, y) of C belongs to A C . Clearly, the total length of P is L. Consider any standard dual arc (v, w) in D G′ . Note that its opposite arc (w, v) exists and has a non-positive length. We now extend P by adding an arc from the s-th copy of v to the (s + 1)-th copy of w and an arc for the (s + 1)-th copy of w to the (s + 1)-th copy of

v, s = |A C | + 1, • • • , k.
Clearly the resulting path P ′ links the first to the (k + 1)-th copy of v and has length L < 0 in (k + 1)D G′ . Suppose now there is a path P of strictly negative length L linking a first to a (k +1)-th copy of a vertex v in (k + 1)D G′ . Let us consider that P contains a proper subpath linking two copies of a vertex w: it covers the case where two arcs in the path linking one copy of

D

G′ to the next one represent the deletion of the same arc in the input graph. Suppose that P admits at least one proper subpath linking two copies of a vertex and whose length is strictly negative, and consider a minimal (inclusion-wise) such subpath P ′ (i.e., no proper subpath of P ′ links two copies of a vertex). If the total length L ′ of P ′ in (k + 1)D G′ is strictly negative, then P ′ corresponds to a circuit C in D G′ , and the set A C of arcs on P ′ that link two vertices in different copies of D G′ is such that |A C | ≤ k, all arcs in A C are standard dual arcs, and the total length of the other arcs on

C is L ′ < 0. Hence G ′ is not k-survivable.
So assume all proper subpaths of P that link two copies of a vertex w have a nonnegative length. Let (v = x 1 , x 2 , . . . , x p = v) be the sequence of vertices visited by P . If P contains two copies x i and x j (j > i) of a vertex with i ̸ = 1 or j ̸ = p, then assume x i belongs to the s-th copy of D G′ , while x j belongs to the s ′ -th copy (s ′ > s). We build a new path P ′ from P by considering the new sequence

(v = x 1 , . . . , x i , x j+1 , x j+2 , . . . , x p = v)
where each x q = w with q ≥ j + 1 that belongs to the s q ≥ s ′ -th copy of D G′ is replaced by the copy of w lying in the (s q + s -s ′ )-th copy of D G′ . Hence, P ′ is a path linking the first to the (k + s -s ′ + 1)-copy of v, and its length is at most L since we have removed a subpath of P of non-negative length. By repeating this process, we obtain a path P * linking the first to the k ′ -th copy of v such that k ′ ≤ k, whose length is at most L < 0 in (k + 1)D G′ , and that does not contain any proper subpath linking two copies of a vertex. Hence, P * corresponds to a circuit C in D G′ and the set A C of arcs on P * that link two vertices in different copies of D G′ is such that |A C | ≤ k, all arcs in A C are standard dual arcs, and the total length of the other arcs on C is strictly negative, which means that G ′ is not k-survivable. □

For illustration of the above theorem, consider the path (f, d, h, g, f ) in the graph 2D G′ of Figure 3.3, with (h, g) as unique arc in this path linking the first to the second copy of

D G′ . The length of this path in 2D G′ is u ut 1 -1 + 0 + 0 = u ut 1 -1, while the corresponding circuit (f, d, h, g, f ) in D G′ has length u ut 1 -1 + u t 2 t 1 + 0 = u ut 1 + u t 2 t 1 -1.
Requiring that the total length of the arcs on P must be non-negative is equivalent to impose u ut 1 ≥ 1, which corresponds to the fact that the arc (t 2 , t 1 ) is possibly removed from A ′ , and the 3.3. TABU SEARCH for larger instances. We propose to apply to this problem a tabu search, which is one of the most frequently used metaheuristics in combinatorial optimization [START_REF] Glover | Tabu search[END_REF]]. The method can be summarized as follows. Let S be the solution space (set of feasible solutions) to a combinatorial optimization problem, and let F be a function to be minimized over S. For a solution s ∈ S, let N (s) denote the neighborhood of s, which is defined as the set of solutions in S obtained from s by performing a local change, called move. A tabu search generates a sequence s 0 , • • • , s q of solutions in S where s 0 is an initial solution and each s i (i = 1, • • • , q) belongs to N (s i-1 ). In order to avoid cycling, the algorithm uses a tabu list that contains forbidden moves. Hence, a move m from s i to s i+1 can only be performed if m does not belong to the tabu list, unless F (s i+1 ) is strictly smaller than the value F (s * ) of the best solution encountered so far. A move belonging to the tabu list has a tabu status until is is removed from it. As stopping criterion, one may use a fixed amount of CPU time, a fixed number of iterations, a fixed gap to a lower bound value or a fixed number of consecutive iterations without improvement of the value F (s * ). More details are given in [START_REF] Glover | Tabu search[END_REF]].

The proposed adaptation of tabu search to CRkECSN can be roughly described as follows. A k-survivable graph is said to be inclusion-wise minimal if the removal of any of its arcs makes it non k-survivable. The solution space S explored by the tabu search is the set of inclusion-wise minimal k-survivable subgraphs G ′ of the input graph G = (V, A).

A move from a solution G ′ = (V, A ′ ) to a solution in its neighborhood is performed as follows. We first remove an arc from A ′ and put a tabu status on this arc in order to avoid the possibility of cycling, by forbidding to select this arc too early in the current solution again. Since G ′ is inclusion-wise minimal, this means that the resulting graph is not k-survivable, and we therefore repair it by adding arcs (different from the arcs which have been recently deleted if those are not necessary to a feasible solution) until we obtain a k-survivable subgraph of G. We then remove arcs in order to get a new inclusion-wise minimal k-survivable subgraph. More details about each phase of such a move are given in the next subsections. We will then be ready to give a more precise description of the proposed tabu search.

TABU SEARCH

into a graph with no feasible flow. There is however possibly another set A ′′′ so that G ′′ = (V, A ′ \ A ′′′ ) has no feasible flow. We therefore repeat the complete process until we obtain a k-survivable subgraph of G. The whole repair procedure is summarized in Procedure Repair. Note that, if the original graph G is k-survivable, then Procedure Repair necessarily produces a set A ′ so that (V, A ′ ) is a k-survivable subgraph of G, since the graph (V, A \ A ′′ ) has a feasible flow for all subsets A ′′ containing at most k arcs of A.

Procedure Repair(A ′ ) Input : A set A ′ ⊆ A of arcs such that G ′ = (V, A ′ ) is not k-survivable; Output: An updated set A ′ ⊆ A of arcs such that G ′ = (V, A ′ ) is k-survivable; 1 Set T oBeRepaired = true; 2 Set A ′′ =TestSurvivability(A ′ ) and G ′′ = (V, A ′ \ A ′′ );

Inclusion-wise minimal solutions

Given a k-survivable subgraph G ′ = (V, A ′ ) of G, we now explain how to remove arcs from A ′ in order to obtain an inclusion-wise minimal solution. Following the notations of Section 2, let D G′ be the graph that contains a negative circuit if and only if G ′ has no feasible flow. For every arc (i, j) ∈ A ′ , we consider its standard dual arc a d ij = (x, y) and determine a shortest path P linking the first copy of y to the (k + 1)-th copy of x in (k + 1)D G′ . Let P ′ be the path in (k + 2)D G′ obtained from P by adding the arc linking the (k +1)-th copy of x to the (k +2)-th copy of y. Clearly, P and P ′ have the same length.

Hence, if P has a negative length, this means that there is a path of negative length in

(k + 2)D
G′ linking the first to the last copy of y, and this path contains an arc linking x to y in different copies of D G′ . In other words, the negative length of P ′ means that there is a graph obtained from G ′ by removing (i, j) and k additional arcs which does not contains a feasible flow. This means that, if (i, j) is removed from G ′ , then the resulting graph is not k-survivable.

If follows that a procedure that transforms G ′ into an inclusion-wise minimal ksurvivable subgraph of G simply consists in considering all standard dual arcs a d ij = (x, y) in D

G′ and determining a shortest path P linking the first copy of y to the (k + 1)-th copy of x in (k + 1)D G′ : if P has a negative length, this means that (i, j) must stay in A ′ since its removal would make G ′ not k-survivable; if P has a non-negative length, then (i, j) can be removed from G ′ .

The procedure that transforms G ′ into an inclusion-wise minimal solution is called MakeMinimal and is described here below.

Note that there are possibly more than one inclusion-wise minimal subgraphs of G ′ , and the order in which the arcs are considered for possible deletion may therefore have an impact on the resulting graph. We suggest an ordering that gives preference to large costs, but with a random component to bring diversity. More precisely, we suggest to first multiply each cost c a by a random number ρ a uniformly chosen in ]0, 1], which gives a new

TABU SEARCH

Procedure MakeMinimal(A ′ )

Input : A subset A ′ ⊆ A of arcs so that G ′ = (V, A ′ ) is k-survivable; Output: An updated subset A ′ so that G ′ = (V, A ′ ) is k-survivable and inclusion-wise minimal; 1 foreach (i, j) ∈ A ′ do 2 Consider the standard dual arc a d ij = (x, y) of (i, j) and compute a shortest path P from the first copy of y to the (k + 1)-th copy of x in (k + 1)D G′ ;

3 if P has a non-negative total length then remove (i, j) from A ′ ;

4 end cost c ′ a = ρ a c a ,
A k such that if A k ∪ {(i, j)}
is removed from G ′ there does not exist a feasible flow between the root and the terminals.

It is useless then to visit in the foreach all arcs of a k ∈ A k because they are obviously necessary to a solution. Therefore, the algorithm is modified in this case to not visit them after.

The proposed tabu search for the CRkECSN

We now describe in more details the proposed tabu search procedure. In what follows, we denote by c(A) = ∑ a∈A c a the total cost of an arc set A.

We first determine whether the input graph G = (V, A) is k-survivable, using the

TestSurvivability procedure. If it turns out that G = (V, A) is not k-survivable, then
there is obviously no feasible solution to the CRkECSN instance, and we therefore stop the procedure. Otherwise, we start the tabu search. The initial solution G ′ = (V, A ′ ) is generated by applying the MakeMinimal procedure to A ′ = A.

Then, given any solution G ′ = (V, A ′ ) visited by the tabu search, we select a subset

S A ′ of ⌈λ|A ′ |⌉ arcs in A ′
, where λ is a parameter whose value belongs to ]0, 1]. For every arc a in S A ′ , we create a new set S a A ′ by first removing a from A ′ , then applying the Repair procedure, and finally running the MakeMinimal procedure to get a set S a A ′ so that (V, S a A ′ )) is an inclusion-wise minimal k-survivable subgraph of G. In order to avoid the presence of the arc a in S a A ′ , we add a temporary penalty M to its cost c a , this penalty being removed when moving to the next arc in S A ′ . Note that it may happen that a necessarily belongs to S a A ′ . For example, if G = (V, A) contains only two vertices, one being the root r and the other a terminal t 1 , and if only two parallel arcs of capacity 1 link r to t 1 , then G is 1-survivable since it contains a feasible flow, even if one of its arcs is removed. However, no proper subgraph of G is 1-survivable. Hence, if one of its arc is removed, the Repair procedure has to add it again to recover 1-survivability. This is the reason why we penalize the insertion of a in S a A ′ instead of forbidding it. For the same reason, the arcs with a tabu status can be required to repair A \ {a}, and they are therefore also considered for insertion into S a A ′ , but with a penalty M .

Once all arcs in S A ′ are treated, the algorithm moves from A ′ to the set S a A ′ with lowest total cost, and the arc a that was removed from A ′ to produce S a A ′ gets a tabu status for the next τ iterations, where τ is a parameter of the method. The algorithm stops when a stopping criterion is met (which will be a time limit in our case). A detailed description of the whole process appears in Procedure TabuSearchCRkECSN.

In order not to always choose the same subset S A ′ of arcs while giving preference to arcs with a large cost, we suggest to use the same kind of techniques as the one proposed for ordering the vertices before applying the MakeMinimal procedure. More precisely, we suggest to compute a value c ′ a = ρ a c a for each a ∈ A ′ , where ρ a is a random number uniformly generated in ]0, 1] (this is done in the computations in Section 3.4). We then sort the arcs a of A ′ by non-increasing values of c ′ a , and include the ⌈λ|A ′ |⌉ first ones in S A ′ .

COMPUTATIONAL EXPERIMENTS

Procedure TabuSearchCRkECSN

Input : A graph G = (V, A) with capacity and cost functions on the arc set u and c respectively, four parameters λ, τ , ρ and M , a positive integer k; Output: A set A * of arcs so that (V, A * ) is inclusion-wise minimal k-survivable, or the message "G = (V, A) is not k-survivable"; 1 if the output of TestSurvivability(A) is an arc set then

Computational Experiments

Several exact algorithms for CRkECSN based on an integer programming formulation is described in Chapter 2. It applies to all graphs, hence also to non planar ones. We compare it to our TabuSearchCRkECSN procedure. All experiments are performed on a computer with a 2.40GHz Intel(R) Core(TM) i7-5500U CPU and 16Gb of RAM, and the integer programs are solved using CPLEX (v12.2).

Tests are performed on instances with |V | ∈ {20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100} vertices, and For the costs, we have chosen values that depend on the length (in the Euclidean plane)

and the capacities of the arcs. More precisely, for two vertices i and j with coordinates (x i , y i ) and (x j , y j ), we have set Column I a indicates the average number of iterations of our tabu search in 45 seconds.

c ij = 1 |T | u ij √ (x j -x i ) 2 + (y j -y i ) 2 ,
We observe that TabuSearchCRkECSN found the optimal solution for all instances solved to optimality by the exact method. Moreover, these optimal solutions were obtained for each of the 10 runs, except in one case. Indeed, for the instance with |V | = 45 vertices and |T | = 44 terminals, our tabu search has found the optimal solution in only 3 of the 10 runs, but the average cost C a = 28.03 is very close to the optimal value C opt = 27.90

(which corresponds to an increase of around 0.5% of the cost). We also note that, when the exact method has produced a proven optimal solution (i.e., T opt < 3000), the average time T a needed by TabuSearchCRkECSN to obtain the same optimal cost is significantly smaller than T opt . For the instances not solved to optimality (i.e., T opt = 3000), the average cost produced by our tabu search is always strictly better than the best cost found by the exact method. We observe that the average number I a of iterations of the tabu search decreases when the number |T | of terminals or the number |V | of vertices increases. For graphs with 100 vertices, less than 100 iterations could be performed, in average, which indicates that more time should probably be allocated so that the tabu search has more chance to find solutions of good quality.

Similar results appear in Tables 3.2 and 3.3 for k = 2 and k = 3, respectively. Among the 53 1-survivable instances, only 31 instances passed the 2-survivability test, and 8 of them passed the 3-survivability test of line 1 in Procedure TabuSearchCRkECSN.

Again, we observe that our tabu search found the optimal solution for all instances solved Up to this point, all instances had an arc (i, j) in A if and only if (j, i) ∈ A, while in practice, it often happens that only one of them exists in the given graph G = (V, A). We have thus decided to also test our tabu search on instances where each edge of the original undirected graphs is oriented in exactly one of the two possible directions. For each of the 53 1-survivable instances ot Table 3.1, we have deleted one of the two arcs (i, j), (j, i)

for each pair of adjacent vertices. The chosen directions were made so that the resulting oriented graphs remained 1-survivable. We have then run our algorithm on these new instances. Clearly, the optimal value for each new instance is at least as large as the value of the same instance where all edges were associated with two arcs with opposite directions.

Results appear in Tables 3.4, 3.5 and 3.6. While 53 new instances were 1-survivable, only 26 of them were 2-survivable, and 4 were 3-survivable. We can observe that the removal of exactly one of the two arcs (i, j), (j, i) for each pair of adjacent vertices has a big impact on the optimal value. For example, for |V | = 35 vertices, |T | = 10 terminals, and k = 3, the optimal solution in Table 3.3 has value 34.76, while the optimal cost C opt is 55.91 in Table 3.6. When comparing C opt with C b we again observe that our tabu search was always able to determine an optimal solution when the exact method stopped with a proven optimal one, except in one case: for the instance with |V | = 90 vertices, |T | = 54 terminals and k = 2, the optimal cost C opt is 93.78, while the best solution produced by 3.4. COMPUTATIONAL EXPERIMENTS our tabu search has cost C b = 94.05 (increase of around 0.2% of the cost), and the average cost is C a = 94.25 (increase of around 0.5% of the cost). Note however that both T a and T b are larger than 40, which means that our tabu search improved the best solution A * less than 5 seconds before the process was stopped. For this particular instance, we have determined that 25 additional seconds would have been sufficient to reach the optimal solution. By allocating 120 seconds instead of 45, we have even been able to reach the optimum in 7 of the 10 runs.

For four instances with k = 1, four with k = 2, and one with k = 3, our tabu search had at least one run out of 10 which did not end with a proven optimal solution. But for all these instances, the mean cost C a is always very close to the optimal cost C opt . Chapter 4

Wind farm cable layout optimization with constraints of load flow and robustness

Introduction

Presentation of the problem

The design of wind farm networks involves many challenges in optimization, see Subsection 0.3.1 in Chapter . In this chapter, we consider the problem of designing a robust cabling network of an offshore wind-farm, at minimal cost, once the location of the turbines has already been decided. The work presented here was carried out in collaboration with an EDF engineer.

More precisely, given a set of offshore wind turbines producing a known quantity of energy, we look for an optimal network able to route the energy produced by all the wind turbines to the point of common coupling (PCC), called root node thereafter in this chapter, that will collect the energy and dispatch it to the grid. One of the main characteristics of our network is that it should be robust, i.e. resilient to the failure of one or several cables: hence, we aim to build the cheapest network that will be able to route, for a given number of any possible breakdowns, all the produced energy from the wind turbines to the root node. An important constraint of our problem is that the flow of energy routed in the network must satisfy the Load Flow equations. We will explain these constraints in 4.1. INTRODUCTION the next section.

We model the problem by using an undirected graph G = (V ∪ {r}, E), where r is the root node, each vertex in V represents either a wind turbine or a junction node between two or more cables, and E is the set of all possible "edges" on which a cable can be installed. The location of the root, of the wind turbines and of the possible junction nodes are known, so the lengths of the edges of E are given. There are different types of electric cables: the cost and capacity of a cable depend on the type of cable chosen and on the length of the cable, and each type is defined by a cost per meter and a capacity.

The design of cabling networks of wind farms has been recently investigated, see Subsection 0.3.1 in Chapter .

In this chapter, we first consider the problem when no breakdown can occur: we present a mathematical model to solve the problem exactly. We give some results obtained on real data. Then we consider the problem in its full generality and present two mathematical formulations for the robust case: the first one, derived from the problem without any breakdowns, is a mixed-integer linear program that considers the case where the number of breakdowns that can occur is 1; the second one is a bi-level mixed integer linear program which is a compact formulation with few variables and constraints. We first explain briefly the Load Flow equations and how to take into account these constraints.

The Load Flow constraints

Approximation of the load flow equations

Load flow studies, also known as power flow studies, are power system analysis. We briefly explain them in this section but we refer the reader to [START_REF] Seifi | Electric Power System Planning: Issues[END_REF] for more information about electrical power system planning, especially Appendix A for the load flow problem. We define a bus as a node of an electrical network (for example 4.1. INTRODUCTION circuit breakers, transformers, conductors or capacitors); in our application, a bus is either an inter-connection node or a wind turbine or the substation. In this chapter, buses are referred to as nodes, and cables between two buses as lines.

Given the production capacities of the different generators (in our application, the generators will correspond to the wind turbines), the load flow equations allow to calculate the electrical state of the network i.e. to determine the voltages, real and reactive power flows, and currents in a system (at each node or cable) under given load conditions. They are used in planning studies to determine if and when electrical devices will become overloaded. They can be used for example to verify that demands are met without overloading the different network facilities or to ensure that maintenance plans (for example taking off a line for replacement) can proceed without undermining the security of the system.

The load flow problem consists in finding the voltage magnitude and phase angle at each node, and the real and reactive power flowing through each line of the network. We define n as the number of nodes in the network. The formulation of the load flow problem requires to consider four variables at each node v = 1, .., n of the network:

• P v : the net active power injection in MW (Mega Watts), which is the difference between active power generation and active power demand at node v

I v = P v -ιQ v |U v | e ιθv , ∀v = 1, .., n (4.2)
where

• ι 2 = -1
• I v is the net injected current at node v and I is the vector (I v ) v=1,..,n

• U is the vector of node voltages

• Y is the nodal admittance matrix of the system, which represents the admittance (measure in Siemens of how easily a device will allow a current to flow) at each node.

I, U and Y have complex components, and

U v = |U v |e ιθv is
P v = n ∑ w=1 |Y vw ||U v ||U w | cos(θ v -θ w -δ vw ) (4.3) Q v = n ∑ w=1 |Y vw ||U v ||U w | sin(θ v -θ w -δ vw ) (4.4) 4.1. INTRODUCTION
To solve these equations, two of the four variables (P , Q, U and θ) must be known in advance at each node. This formulation results in a non-linear system of equations which requires iterative solution methods. However, for such methods, convergence is not guaranteed.

In Using Assumptions A and C and 4.3, we have for each v = 1, .., n:

P v = n ∑ w=1 |Y vw ||U v ||U w | cos(θ v -θ w -δ vw ) = n ∑ w=1 B vw cos(θ v -θ w - π 2 )
Using cos(θ v -θ w -π 2 ) = sin(θ v -θ w ) and Assumption B we have for each node v in 4.1. INTRODUCTION the system:

P v = n ∑ w=1 B vw (θ v -θ w ) (4.5)

Integration of the Load Flow equations in our problem

Regarding the design of a wind farm, we consider here a non-directed graph G = (V, E)

where V is the set of n nodes of the network (i.e. the substation r, the wind turbines and the interconnection nodes) and E is the set of edges where we can build a cable. In the following, we will refer to the substation r as the root. We are given for each edge [v, w] ∈ E a susceptance B vw . However, if we do not build a cable on the edge [v, w] in the final network, we can set B vw to 0. We also consider ⃗

G = (V, ⃗ E) which is the bi-directed graph associated with G (i.e. for each edge [v, w] ∈ E in G, there are the arcs {(v, w), (w, v)} ⊂ ⃗ E in ⃗ G).
For each node v different from the root node (i.e. v ∈ V \ {r}), it is known that P v ≥ 0:

either P v > 0 if v provides some power injection in the network (i.e. v is a wind turbine in our case), or P v = 0 if v is a junction node. If v is a wind turbine, P v is known and gives the estimation of the production of energy of the wind turbine v. For the root r, the load flow equations imply that P r = -∑ v∈V \{r} P v . For each (v, w) ∈ ⃗ E, we define:

Π vw := B vw (θ v -θ w )
as the active power flow through [v, w] from v to w, and thus we have Π vw = -Π wv and Since P v ′ > 0, P v ≥ 0 ∀v ∈ V \ {r}, and r / ∈ V ′ , we have S > 0. However, using Equation (4.5), we also have:

P v = ∑ n w=1 Π vw . Property
S = ∑ v∈V ′ P v = ∑ v∈V ′ ∑ w∈V ′ Π vw = 0
since Π vw = -Π wv . Hence a contradiction. □ Property 4.1.1 ensures that if Constraints 4.5 are satisfied in a mathematical program, we do not have to add connectivity constraints to ensure that there exists a path between the root and each wind turbine, since load flow equations will not be satisfied otherwise.

The approximation of the load flow analysis will be used to ensure that, for each feasible solution, the power routed through the cables will not exceed its capacity.

The problem without breakdowns

In this section, we present the problem when no breakdown can occur on the cables. We first give a mixed-integer linear model to solve the problem, then we present a heuristic to get a good feasible solution. In the following, we are given P v for every node different from the root node. We recall that if v ∈ V represents a wind turbine, then P v corresponds to the active power produced and collected through the network by the wind turbine, otherwise v is either a junction node and P v = 0 or the root node r and P r is not defined

(technically it is equal to - ∑ v∈V \{r} P v ).

Mathematical formulation

In practice, the given undirected support network, G = (V, E) is often the union of a partial grid on n nodes, of some diagonal edges and of the root node linked to a subset of vertices of the grid. Let (i, j) be the position of a vertex v in the grid, a diagonal edge 4.2. THE PROBLEM WITHOUT BREAKDOWNS incident to v is an edge linking v to another vertex at the position (i+1, j +1), (i+1, j -1), (i -1, j + 1) or (i -1, j -1); see Figure 4.1 for an example. The set of wind turbines is denoted by T ⊂ V \ {r}. Hence V \ (T ∪ {r}) denotes the set of junction nodes. We also consider Q different types of electrical cables numbered by q ∈ [1, ..., Q]; Q is generally a small number (≤ 3). For each q ∈ [1, ..., Q] and each [v, w] ∈ E, we denote by c q vw , the cost of installing a cable of type q on [v, w]. This cost depends on the type of cable chosen and on the length of [v, w]. The capacity of a cable of type q on [v, w] is denoted by u q vw (c q vw = c q wv and u q vw = u q wv ). Hence, we aim to design the cheapest network such that the capacity on each installed cable is greater than the active power flow routed through this cable, i.e. Π uv ≤ u q uv and Π vu ≤ u q uv for each edge [u, v] where a cable of type q is installed. Notice that the network must verify the load flow equations. For technical constraints given by EDF, there is a set I ⊂ E × E of pairs of edges {e, e ′ } such that it is not allowed to install a cable on both e and e ′ . In practice, the set I is used to avoid installing cables on two edges that intersect each other, and hence to ensure that the resulting network is planar (on Figure 4.1, we would have for example {e 1 , e 2 } ∈ I because e 1 and e 2 are crossing diagonal edges).

Variables and constraints

Recall that the power injection P v at node v ∈ V is given for each vertex v. Moreover, B q vw , corresponding to the susceptance of a cable of type q between v and w, is also given for each [v, w] ∈ E and each q ∈ [1, .., Q].

THE PROBLEM WITHOUT BREAKDOWNS

We introduce the following variables:

• For each q ∈ [1, ..., Q] and for each e = [v, w] ∈ E, let y q e be the binary variable such that y q e = 1 if and only if a cable of type q is installed on e = [v, w]. Notice that, in the following, for each e = [v, w] ∈ E, y q e can be written indifferently y q e , y q vw or y q wv .

• For each v ∈ V , let θ v be the voltage angle at v.

We now introduce the different constraints associated with our problem:

Cable types constraints:

For each e ∈ E, we cannot install more than one type of cable:

Q ∑ q=1
y q e ≤ 1, ∀e ∈ E (4.6)

Constraints of incompatibility between edges:

The set I ⊂ E × E contains every pair {e 1 , e 2 } such that there cannot be a cable on both edges e 1 and e 2 : Q ∑ q=1 (y q e 1 + y q e 2 ) ≤ 1, ∀(e 1 , e 2 ) ∈ I (4.7)

Voltage angles constraints:

In the load flow equations, we only consider the differences of angles θ v -θ w for each pair (v, w) ∈ V 2 with v ̸ = w, i.e. the value of θ v alone is useless. Using this fact and Assumption B, which states that voltage angles are assumed to be small, we can fix arbitrarily and without loss of generality the value of the angle at the root node r: θ r = 0 (4.8) Therefore, since, by Assumption B, for any v, w ∈ V , θ v -θ w is very small, we have that, for all v ∈ V , -ε ≤ θ v -θ r ≤ ε for some small ε > 0, which implies:

-ε ≤ θ v ≤ ε ∀v ∈ V
Differences of voltage angles are assumed to be less than 10 -1 , hence we have ε ≈ 10 -1 .

THE PROBLEM WITHOUT BREAKDOWNS

Load Flow constraints:

For all v ∈ V , the load flow equations are given by:

P v = Q ∑ q=1 ∑ w:[v,w]∈E
B q vw y q vw (θ v -θ w ) (4.9)

where

Q ∑ q=1
B q vw y q vw (θ v -θ w ) = Π vw corresponds to the active power sent through (v, w) ∈ ⃗ E. In other words, the load flow constraints ensure that each wind turbine is connected to the root, and allow to calculate the power routed through each cable.

Power line constraints:

For each e ∈ E, the power flow Π e routed through e must be smaller than the capacity of the cable installed on e:

Q ∑ q=1 B q vw y q vw (θ v -θ w ) ≤ Q ∑ q=1
u q vw y q vw ∀(v, w) ∈ ⃗ E (4.10)

One can notice that, if

Q ∑ q=1
B q vw y q vw (θ v -θ w ) < 0 (resp. > 0), then

Q ∑ q=1
B q wv y q wv (θ w -θ v ) > 0 (resp. < 0), depending on whether the energy is routed from v to w or from w to v.

Mathematical program

We aim to minimize the total cost of the resulting network, i.e.: min

∑ e∈E Q ∑ q=1 c q e y q e
We introduce E I the set of edges e with at least one constraint of incompatibility with another edge, i.e. e ∈ E I if there exists at least one edge e ′ such that {e, e ′ } ∈ I. The mathematical program to solve can be written as follows:

4.2. THE PROBLEM WITHOUT BREAKDOWNS (LFF)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y,θ ∑ e∈E Q ∑ q=1
c q e y q e s.c.

Q ∑ q=1 y q e ≤ 1, ∀e ∈ E \ E I Q ∑ q=1
(y q e 1 + y q e 2 ) ≤ 1, ∀(e 1 , e 2 ) ∈ I Using Property 4.1.1, Constraints 4.9 ensure the connectivity between the root and the wind turbines, while Constraints 4.10 ensure that no cable is overloaded.

θ r = 0 Q ∑ q=1 ∑ w:[v,w]∈E B q vw y q vw (θ v -θ w ) = P v , ∀v ∈ V \ {r} Q ∑ q=1 B q vw y q vw (θ v -θ w ) ≤ Q ∑ q=1 u q vw y q vw , ∀(v, w) ∈ ⃗ E y ∈ {0, 1} |E|Q , θ ∈ [-ε, ε] |V |

Linearization of the program

One can notice that the above program have non-linear terms, y q vw θ v and y q vw θ w in Constraints 4.9 and 4.10. Since -ε ≤ θ v ≤ ε ∀v ∈ V , we have that 0 ≤ θ v + ε ≤ 2ε for each v ∈ V \ {r}. We can now propose a well-known solution, to linearize each term y q vw (θ v + ε) which is the product of a binary variable by a non-negative bounded real variable, see for instance [START_REF] Billionnet | Optimisation Discrète, de la modélisation à la résolution par des logiciels de programmation mathématique[END_REF]]. For all (v, w) ∈ ⃗ E, q ∈ [1, ..., Q], we introduce a non-negative variable ρ q vw and the following polyhedron:

L(θ, y) = ⎧ ⎪ ⎨ ⎪ ⎩ ρ ∈ R | ⃗ E|Q ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ρ q vw ≤ θ v + ε ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q] ρ q vw ≤ 2εy q vw ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q] ρ q vw ≥ θ v + ε -2ε(1 -y q vw ) ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q] ⎫ ⎪ ⎬ ⎪ ⎭
We have:

ρ ≥ 0, ρ ∈ L(θ, y) ⇒ ρ q vw = y q vw (θ v + ε) ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q]
Notice that, for each edge [v, w] and each cable type q ∈ [1, .., Q], we have ρ q vw = y q vw (θ v +ε) while ρ q wv = y q vw (θ w +ε). Products between θ and y only appear in our problem 4.3. ROBUST APPROACH in the form y q vw (θ v -θ w ) with (v, w) ∈ V 2 . Since we have y q vw (θ v -θ w ) = y q vw θ v -y q vw θ w = y q vw (θ v + ε) -y q vw (θ w + ε), we also have y q vw (θ v -θ w ) = ρ q vw -ρ q wv . We can then linearize the mathematical program:

(LLFF)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y,θ,ρ ∑ e∈E Q ∑ q=1
c q e y q e s.c.

Q ∑ q=1 y q e ≤ 1, ∀e ∈ E \ E I Q ∑ q=1
(y q e 1 + y q e 2 ) ≤ 1, ∀(e 1 , e 2 ) ∈ I

θ r = 0 Q ∑ q=1 ∑ w:[v,w]∈E
B q vw (ρ q vw -ρ q wv ) = P v , ∀v ∈ V \ {r}

Q ∑ q=1 B q vw (ρ q vw -ρ q wv ) ≤ Q ∑ q=1 u q vw y q vw , ∀(v,

Robust approach

In this section we consider that a breakdown may occur on one or several installed cables. We denote by k the maximal number of breakdowns that may occur simultaneously in the network.

The case k = 1

Let us denote by ξ ∈ E the cable where the breakdown occurs. We introduce the following variables:

ROBUST APPROACH

• For each q ∈ [1, ..., Q] and for each e ∈ E, let y q e be the binary variable such that y q e = 1 if and only if a cable of type q is installed on e.

• For each v ∈ V and each ξ ∈ E, let θ ξ v be the voltage angle at v in the network where no power can transit through ξ.

We introduce ⃗ ξ for ξ ∈ E as the set of bi-directed arcs associated with the edge ξ. We propose the following mathematical program to design an optimal network which is robust to one breakdown:

(κ)

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ min y,θ ∑ e∈E Q ∑ q=1
c q e y q e s.c.

Q ∑ q=1 y q e ≤ 1, ∀e ∈ E \ E I Q ∑ q=1
(y q e 1 + y q e 2 ) ≤ 1, ∀(e 1 , e 2 ) ∈ I In this formulation, θ ξ v represents the voltage angle at the node v in the current network when there is a breakdown on the cable built on the edge ξ: we aim to ensure that the load flow equations are satisfied when we cannot route any power flow through this cable.

θ ξ r = 0 ∀ξ ∈ E Q ∑ q=1 ∑ [v,w]∈E\{ξ} B q vw y q vw (θ ξ v -θ ξ w ) = P v ∀v ∈ V \ {r}, ∀ξ ∈ E Q ∑ q=1 B q vw y q vw (θ ξ v -θ ξ w ) ≤ Q ∑ q=1 u q vw y q vw ∀ξ ∈ E, ∀(v, w) ∈ ⃗ E \ { ⃗ ξ} y ∈ {0, 1} |E|Q , θ ∈ [-ε, ε] |V ||E|
Constraints (4.11) and (4.12) are identical to (4.6) and (4.7), while Constraints (4.13) ensure that θ r is equal to 0 for each case of breakdown ξ ∈ E. Constraints (4.14) ensure that the load flow is respected (and so each turbine is connected to the root) for any breakdown ξ ∈ E by not considering the active power on ξ in this case. Indeed, for each scenario of breakdown on a cable built on the edge ξ ∈ E, we do not consider in Constraints (4.14) the edge ξ in the calculation of the sum of energy leaving v, which is equivalent to not 4.3. ROBUST APPROACH considering the cable built on ξ. Constraints (4.15) then ensure that, for any breakdown on ξ ∈ E, the capacities in the resulting network are high enough to support the active power through the cables. The program above hence computes a network of minimal cost which is robust to one breakdown.

Again, we have a product of variables θ and y, which we linearize in a similar way as in the non-robust model. We introduce L ξ (θ, y), which is the linearization of the product y q uv (θ ξ v +ε), where y q uv is a binary variable and (θ ξ v +ε) is a non-negative variable, considering the robust case:

L ξ (θ, y) = ⎧ ⎪ ⎨ ⎪ ⎩ ρ ∈ R | ⃗ E||E|Q ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ρ q,ξ vw ≤ θ ξ v + ε ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q], ∀ξ ∈ E ρ q,ξ vw ≤ 2εy q vw ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q], ∀ξ ∈ E ρ q,ξ vw ≥ θ ξ v + ε -2ε(1 -y q vw ) ∀(v, w) ∈ ⃗ E, ∀q ∈ [1, .., Q], ∀ξ ∈ E ⎫ ⎪ ⎬ ⎪ ⎭
The linearized problem becomes:

(Lκ) (y q e 1 + y q e 2 ) ≤ 1, ∀(e 1 , e 2 ) ∈ I Even for k = 1, the number of constraints and columns of (Lκ) can be very high depending on the size of the graph. We propose a constraints generation algorithm similar to the one described in Subsection 2.2.2 in Chapter 2 to deal with this case. We initialize (Lκ) E S which corresponds to (Lκ) with only a small subset of edges E S ⊂ E in Constraints The formulation (κ-sub) e allows to determine whether if the load-flow constraints are still satisfied if we remove the edge e from the current integer solution, i.e. to ensure that the solution is resilient to a breakdown on e. Indeed, if there is no feasible solution to (κ-sub) e , it means that there are no solutions respecting both the load-flow equations and the capacity constraints if we remove the cable on the edge e. We already ensure that the energy is still routed to the sub-station even in the event of a breakdown on any edge in ÊS , and we have to ensure that this is the case for edges in ÊC \ ÊS . When an integer solution better than the current one is found, we then solve the set of sub-problems (κ-sub) e for e ∈ ÊC \ ÊS . If one subproblem (κ-sub) ē for a given ē ∈ ÊC \ ÊS does not have any feasible solution, we add ē to E S and we add the constraints associated to (Lκ) E S . Otherwise, if all subproblems have feasible solutions, the integer solution is feasible for the general problem. Please note that the subproblems (κ-sub) e have only continuous variables.

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐
θ ξ r = 0 ∀ξ ∈ E Q ∑ q=1 ∑ [v,w]∈E\{ξ} B q vw (ρ q,ξ vw -ρ q,ξ wv ) = P v , ∀v ∈ V \ r, ξ ∈ E Q ∑ q=1 B q vw (ρ q,ξ vw -ρ q,ξ wv ) ≤ Q ∑ q=1 u q vw y q vw ∀(v, w) ∈ ⃗ E, ξ ∈ E ρ ∈ L ξ (θ,

Bilevel formulation

In this subsection, we give a bilevel formulation for the general case where the number of breakdowns is bounded by k, which is similar to the one proposed in Subsection 2.2.3 of Chapter 2. The bilevel formulation proposed here is also particular in that the second level is a max min problem (it can be seen as a game with a defender and an attacker).

For each [i, j] ∈ E, we introduce a binary variable b ij where b ij = 1 if and only if the attacker chooses to delete the arc (i, j). The variables y and θ are defined as in Subsection 4.2.2. We also introduce the variables η v for each v ∈ V \ {r}, which correspond to penalty variables used to satisfy the load flow equations. We define the following polyhedron:

4.3. ROBUST APPROACH B(y) = { b ∈ {0, 1} |E| | ∑ [i,j]∈E b ij ≤ k ; b ij ≤ ∑ q∈Q y q ij ∀[i, j] ∈ E }
which defines the set of possible scenarios of edge deletions (i.e. the set of constraints of the attacker): at most k edges can be deleted, and those edges must belong to the ones selected by the defender. We also introduce for each [i, j] ∈ E and q ∈ Q the notation

β q ij = B q ij (y q ij -b ij )
where β ij is equal to B q ij if a cable of type q is built by the defender on the edge [i, j] and not deleted by the attacker, and to 0 otherwise (since we have b ij ≤ ∑ q∈Q y q ij ).

We then define another polyhedron: and the attacker has deleted some edges. We have that β corresponds to the susceptances in the residual network defined by (y, b). Furthermore, at this point we consider that y and b have already been fixed, so β is not a variable. The variables η v are penalty variables which ensure that the polyhedron is non-empty: the solution where we have θ v = 0 and η v = P v for each vertex v is always feasible. The load flow and capacity constraints are satisfied if there exists a feasible solution with ∑ v∈V η v is equal to 0.

X (y, b) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ θ r = 0 Q ∑ q=1 ∑ [v,w]∈E β q vw (θ v -θ w ) + η v = P v ∀v ∈ V \ r β q vw (θ v -θ w ) ≤ u q vw ∀(v, w) ∈ ⃗ E, ∀q ∈ Q η ∈ R |V |-1 + , θ ∈ [-ε, ε] |V | ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭

RESULTS ANALYSIS

We propose the following bilevel program:

(BIL) The defender first builds a network considering the constraints on the number of cables between two nodes and the planarity constraints given by Constraints (4.20a) and (4.20b) respectively. Then, the attacker deletes a set of at most k edges that the defender has built. Then, the defender ensures that the load flow and capacity constraints are still satisfied: he minimizes ∑ v∈V η v , which is a sum of positive variables. If this sum is equal to 0, it means that the load flow and capacity constraints are still satisfied; if it is strictly positive, it means that the load flow constraints and the capacity constraints cannot be satisfied at the same time.

⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ⏐
An intuition for the solving method is to dualize the min problem in the second level in order to reformulate the max min problem into a max problem and use a constraints generation algorithm similar to the one proposed in Subsection 2.2.3 in Chapter 2.

Results analysis

In this section, we present the results of the formulations proposed for the design of wind farm cabling networks with load flow constraints. All experiments were performed on a computer with a 2.40GHz Intel(R) Core(TM) i7-5500U CPU and 16GB RAM, using the solver CPLEX version 12.6.1, interfaced with Julia 0.6.0. We used in particular the package JuMP, a tool allowing mathematical modeling. For each test, the algorithm has 4.4. RESULTS ANALYSIS has not been found in 3000 seconds).

In Table 4.1, the formulation for the non-robust case allows to solve exactly the problem for all instances with a number of wind turbines of at most 35, except for data 35 with |Q| = 3 where it founds an integer solution within a gap of at most 0.04 to the optimal solution. For data 53 , the final gap is 0.02 for |Q| = 1, 0.06 for |Q| = 2 and 0.14 for |Q| = 3.

The solving time or the final gap logically increase with the number of types of cables available, but the formulation still manages to find a solution within a reasonable gap from the optimum value.

For the robust case with k = 1, the formulation is efficient especially for |Q| = 1, where it solves all the instances to the optimum except data 53 , where the gap between the best integer solution and the optimal value is 8%, which sounds reasonable in this case. For |Q| = 2, the formulation gets slower and is not efficient on data 53 . However, it allows to solve optimally data 10 and data 28 and find an integer solution guaranteed to be within a really small gap of the optimum (0.3 %). For data 35 , the final gap is 10%. For |Q| = 3, the formulation is not efficient on data 35 and data 53 but find an integer solution which is optimal or at least close to the optimal value (gaps of 4% and 2%).

The robust formulation has a number of variables |E| times bigger than the one of the non-robust one, which logically explains why it is importantly slower. Furthermore, each incrementation of |Q| adds 3|E| variables for the non-robust formulation and 2|E||E| + |E| variables for the robust formulation with k = 1. Logically, the incrementation of |Q| has thus a higher impact on the robust formulation. Furthermore, the case where |Q| = 1 corresponds to the case with uniform capacities, which appears to be easier to solve.

CONCLUSION

ing is a more constrained version of CRkECSN, where we want to design a network which is resilient to the deletion of any subset of k arcs and such that the resulting flow must be routed from the root to the terminals through an arborescent sub-network (after these k arcs have been deleted). We have begun to investigate this problem for k = 1 on grid graphs with uniform capacity constraints and have found several properties for particular cases. The problem appears to be more difficult to solve than CRkECSN, since the constraint that the flow must be routed through an arborescent sub-network for each scenario of arc deletions seems more difficult to formulate than CRkECSN.

We can also investigate the bilevel program proposed in Chapter 4. This formulation proposes interesting challenges. Bilevel programming formulations are currently widely used in the literature, and our formulation for the second level using slack variables has a number of variables smaller than the one we have tested in this thesis. Once that the min problem has been dualized in the second level, it can be interesting to study different ways to solve this formulation.

Another aspect of the real instances that could be interesting to investigate is the stochasticity. For offshore wind farms with equivalent power, the energy produced by each wind turbine is almost always the same, and hence we have considered a fixed energy production at each turbine. However, the actual production depends partly on the demands or, in wind farm networks, on the amount of wind, and it would be an interesting issue to take this uncertainty into account.

  Keywords : Operations Research, Combinatorial optimization, Robust networks design, Graph theory, Mixed integer programming, Wind farm cabling networks.

  3 en introduction), en respectant les capacités indiquées sur les arcs. Formellement, RÉSUMÉ LONG nous définissons le problème suivant: Problème de réseau de Steiner enraciné k-arc connecté avec contraintes de capacité (CRkECSN) INSTANCE : Un digraphe connecté G = (V, A, r, T, u, c) avec un ensemble de sommets V , un ensemble d'arcs A, une racine r ∈ V , un ensemble de terminaux T ⊆ V \ {r}, une fonction de capacité entière u sur A, une fonction de coût c sur A, un entier k à 1 ≤ k ≤ |A| -1.

Fact

  Trouver un flot qui achemine une unité de flux entre r et chaque terminal dans le graphe d'entrée équivaut à trouver un flot de valeur |T | entre r et s dans le graphe transformé avec le puits et les arcs fictifs. Nous proposons alors une formulation bi-niveau pour résoudre ce problème. La formulation bi-niveau proposée ici est particulière dans la mesure où le deuxième niveau est un problème min max. Il peut être vu comme un jeu avec un défenseur et un attaquant RÉSUMÉ LONG (correspondant respectivement au leader et au suiveur).

  polyèdre X (y, b) correspond à l'ensemble des flots possibles sur le sous-graphe de G induits par les arcs (i, j) ∈ A tels que y ij = 1, s'ils n'ont pas été supprimés, soit b ij = 0. Le polyèdre X (y, b) est défini par les contraintes de conservation du flot, les contraintes de capacité et les contraintes imposant un flot égal à 0 sur tout arc qui est supprimé. Nous définissons également le polyèdre suivant : B = { b ∈ {0, 1} |A| | ∑ (i,j)∈A b ij ≤ k ; b ts = 0 ∀t ∈ T } Le polyèdre B définit l'ensemble des scénarios possibles de défaillances d'arc (il garantit qu'aucun arc fictif ne peut être supprimé). Nous proposons le programme bi-{(i, j) | y ij = 1} définit l'ensemble des arcs sélectionnés. Au niveau supérieur, le RÉSUMÉ LONG défenseur sélectionne l'ensemble des arcs à ajouter au réseau, en choisissant une valeur de y dans {0, 1} A . L'attaquant supprime alors certains arcs en définissant la variable b ∈ B afin de minimiser le flot maximum que le défenseur calculera en définissant la variable x dans le polyèdre de flot X (y, b). Le but du défenseur est de s'assurer que ce flot est au moins égal à |T | (voir Contrainte (2a)). Considérons le problème max dans le niveau inférieur : à ce stade, y et b sont déjà fixés ; nous appelons leurs valeurs ŷ et b respectivement. Le problème est un problème de maxflow de r à s, avec deux ensembles de contraintes de capacité. Dans notre problème, le flot doit être entier puisqu'il correspond à un certain nombre de terminaux. Cependant, il est bien connu que la matrice des coefficients M dans la formulation de l'arc d'un max-flow est totalement unimodulaire (voir Sous-section 0.2.2 dans l'introduction). Ensuite, ajouter le second ensemble de contraintes de capacité équivaut à ajouter la matrice d'identité à M : la matrice reste totalement unimodulaire et, puisque les capacités sont entières, on s'assure que les points extrêmes du polyèdre défini par X (y, b) ont des coordonnées entières. Ainsi, nous pouvons relâcher les contraintes d'intégralité sur x. Dans le problème max du niveau inférieur (i.e. max x∈X (y,b) ∑ j∈Γ + (r) x rj ), il existe toujours un flot réalisable de valeur 0 et le problème est aussi trivialement borné par |T |.

  est le dual du problème max x∈X (y,b)

  µ, γ) ∈ D A ce stade, b est une variable, donc la fonction objectif est non linéaire. Nous linéarisons les termes b ij γ ij de manière classique en introduisant des variables l ij = b ij γ ij où l ij vérifie l'ensemble des contraintes définies par L(b, γ) :

  b,λ,γ,µ,l g(y, λ, γ, l)s.t. b ∈ B (λ, µ, γ) ∈ D l ∈ L(b, γ)On peut alors considérer l'enveloppe convexe du polyèdre de second niveau définie parB, D et L(b, γ),et désigner par H l'ensemble de ses points extrêmes. On peut remarquer que cette enveloppe convexe ne dépend pas de y (g(•) seulement) : l'ensemble des points extrêmes H reste le même pour chaque y ∈ {0, 1} A . Nous désignons par ( λh , γh , lh ) les valeurs respectives de (λ, γ, l) au point extrême h ∈ H. Nous pouvons ensuite reformuler la formulation à deux niveaux en une formulation à un seul niveau comme suit :

∑

  (i,j)∈δ + (S) u ij . We recall the well-known following theorem: Theorem 0.2.2 (Max-flow min-cut theorem [Ford and Fulkerson 1956]) In a network with a root r and a sink s, the minimum capacity of a r-s cut is equal to the maximum value of a feasible flow from r to s.

Theorem 0. 2 . 3 (

 23 Integrality Theorem [Ahuja, Orlin, and Magnanti 1993]) If all capacities in a network are integer, then there exists a maximum flow in which the amount of flow on each arc is integer. Furthermore, a maximum flow can be partitioned into flows of integer values along paths from the root to the sink.

  Let A be a totally unimodular m × n matrix and let b ∈ Z m . Then the polyhedron P = {x|Ax ≤ b} is integer. 0.2. PRELIMINARIES We have the following property and theorem on the totally unimodular matrices: Property 0.2.1 Let A be a totally unimodular m × n matrix and I m the m × m identity matrix. We have that -A, A ⊤ and [A|I m ] are totally unimodular matrices.

  Figure 1: Example of graph transformation for the vertex v

  When taking into account the arc capacities, Papadimitriou shows that the problem is N P-Hard in the spanning case (i.e. all vertices except the root are terminals) [Papadimitriou 1978]. The problem has been studied in the spanning case, and branch-and-bound 0.3. PREVIOUS WORK as well as branch-and-price algorithms have been proposed [Chandy and Lo 1973; Uchoa, Fukasawa, Lysgaard, Pessoa, De Aragao, and Andrade 2008]. Jothi and Raghavachari [Jothi and Raghavachari 2005] and Arkin et al. [Arkin, Guttmann-Beck, and Hassin 2012] propose approximation algorithms when capacities are uniform. Regarding Steiner arborescence problems with capacity constraints, Bentz et al. study the complexity and approximation considering several parameters like the number of terminals, the arc costs and the capacities [Bentz, Costa, and Hertz 2016]. Goemans and Myung propose several Steiner tree formulations [Goemans and Myung 1993]. Bousba et al. solve the Steiner arborescence problem with capacities and demands, which is a generalization of the Steiner tree problem with capacities [Bousba and Wolsey 1991]:

  polyhedral structure of the problem and propose a cutting plane algorithm based on those results. Mixed Integer Linear Programs for solving those problems often consist in formulations based on the cut-sets of the input graphs. Magnanti and Raghavan [Magnanti and Raghavan 2005] propose a formulation for NDC in the case of edge-disjoint paths based on multi-commodity flows. They show that this formulation is stronger than the one us-0.3. PREVIOUS WORK ing cut-set. A method based on Benders decomposition is proposed by Botton et al. for a problem with hop-constraints (the lengths of the different paths between vertices with connectivity requirements should not exceed a given parameter) [Botton, Fortz, Gouveia, and Poss 2013]. Kerivin and Mahjoub give a survey on this type of problems [Kerivin and Mahjoub 2005].One of the main problems we study is called the Capacitated Rooted k-Edge Connected Steiner Network Problem: we aim to design a network of minimum cost in which, after the deletion of any set of k arcs, we can still find a feasible flow (i.e. a flow respecting the capacities) routing one unit of flow from the root to each terminal.Grotschel et al. study

  and let w be the predecessor of v in the path from r to v in S. If we remove (w, v) from A S and add (r, v), we obtain a new spanning arborescence at least as good as S, since we have replaced a subarborescence by two subarborescences of smaller sizes. Doing so for each v ∈ Γ G (r) with (r, v) / ∈ A S yields a solution S * verifying the property. The proof is similar for RStA, by replacing Γ G (r) by V * S ∩ Γ G (r): if we remove (w, v) from A S and add (r, v), we obtain a new Steiner arborescence at least as good as S, since we have replaced a subarborescence by two subarborescences spanning at most the same number of terminals. □ Notice that the property does not hold if we have capacity constraints, because the capacity of (r, v) can be smaller than the one of (w, v) in the proof above. Let us now introduce the feasibility problem associated with RSpA: Robust Spanning Arborescence Feasibility problem (RSpAF) INSTANCE: A connected graph G = (V, E, r) with r ∈ V and an integer β with 1 ≤ β ≤ |V | -1.

  3m, and a positive integer B such that ∑ i=1,...,3m d i = mB and B/4 < d i < B/2 ∀i = 1, ..., 3m. QUESTION: Can D be partitioned into m disjoints subsets M 1 , M 2 , ..., M m of three 1.2. DEFINITION OF PROBLEMS AND COMPLEXITY RESULTS elements such that the sum of the numbers in each subset is equal to B?To obtain an instance of RSpAF from an instance of 3-Partition, we set β = B + 1 and we construct the following graph G = (V, E): we define a root r and m vertices v j with an edge [r, v j ] for j = 1, ..., m, each vertex v j corresponding to a set M j . We add 3m vertices w i and the edges [v j , w i ] for all j = 1, .., m and all i = 1, .., 3m, each vertex w i corresponding to the element d i of D (the subgraph induced by the vertices v j and w i is complete bipartite). Finally, for each i = 1, .., 3m, we add d i -1 vertices adjacent to w i : the subgraph induced by those vertices and the vertices w i is made of 3m disjoint stars.SeeFigure 1.1 for a graph representation of a 3-Partition instance with m = 2, B = 11 and D = {5, 3, 4, 3, 4, 3}. Notice that |V | = 1 + m + mB. Solving RSpAF on G with β = B + 1 amounts to finding an arborescence where the size of the subarborescence rooted at each v j is smaller than or equal to B + 1. If there is a solution to RSpAF on G, then, from the proof of Property 1.2.1, there is a solution S such that (r, v j ) ∈ S ∀j = 1, ..., m, and each w i is connected to exactly one v j , otherwise there is a cycle. Given a vertex v ∈ S, let S(v) be the subarborescence of S rooted at v: ∀j = 1, ..., m, we have |S(v j )| ≤ B + 1 and ∑ j=1,..,m |S(v j )| = |V \ {r}| = mB + m. Thus, ∀j = 1, ..., m, |S(v j )| = B + 1 and S(v j ) contains v j and several vertices w i , each having

Figure 1

 1 Figure 1.1: Graph and RSpAF solution resulting from the 3-Partition instance in which m = 2, B = 11, D = {5, 3, 4, 3, 4, 3}

  and u a positive integer function on E.

  Figures 1.2, 1.3, 1.4 and 1.5 allow to visually compare the arborescences obtained according to the different models for the fourth data set (the filled circles correspond to terminals).

Figure 1 .

 1 Figure1.2 gives an optimal (non robust) capacitated Steiner arborescence (optimal solution of CStA); let us denote its cost by C * . This arborescence cannot be qualified as robust since, in the worst case, all terminals can be disconnected by deleting the only arc incident to the root. Furthermore, the tree has a large depth, and hence the balanced robustness is not good either. This proves the importance of searching for a more robust solution. We consider first the worst case, RCStA, and we denote by R * the best robustness, i.e., the minimum value of the loss of terminals in the worst case of a single arc deletion. See Figure1.3 for the associated solution on the test instance. Then, to obtain the minimum cost of a most robust solution, denoted by C * R * , we solve CStA bounded-robust with R = R * : notice that the constraint is saturated in any feasible solution. Then, ∆ Crob = (C * R * -C * )/C * represents the "cost of robustness", i.e., the percentage of augmentation of the cost to get a robust solution.

1. 3 .

 3 Figure 1.2: Resulting arborescence for the fourth data set for CStA

Fact 2 .

 2 1.1 Finding a flow which routes one unit of flow between r and each terminal in the input graph is equivalent to finding a flow of value |T | from r to s in the transformed 2.2. FORMULATIONS graph with the sink and the fictive arcs.

Figure 2

 2 Figure 2.1: Example of addition of a sink to the input graph

  itated arcs. If this capacity is smaller than |T |, we add the constraints associated with S, otherwise the algorithm terminates. For small values of k, one straightforward method to find this cut of minimum residual capacity is the following: for each combination C of k arcs in A I which are selected in the current solution, compute the min-cut on the graph where the capacity of each arc (i, j) is defined as u ij ŷij , except for the k arcs of C whose capacities are set to 0. Otherwise, if k is too big, we use the following MIP, where  = {(i, j) ∈ A | ŷij = 1} and Ĝ = (V, Â) corresponds to the current solution:

  in the polyhedron X (y, b) to make the 2.2. FORMULATIONS resulting polyhedron X (y, b) more compact. However, if for a given (i, j), we have b ij > y ij (i.e. b ij = 1 and y ij = 0), then X (y, b) is empty and hence min b∈B max x∈ X (y,b)

  14b) Property 2.3.1 (SL) and (RSL) have the same optimal values.

Figure 2 . 2 :

 22 Figure 2.2: Graph where Inequalities (2.24a) and (2.24b) cut some non-integer solutions

  |V |, terminals |T |, and edges |E|. All instances have been generated in the following way: the vertices have been randomly generated in the plane, and the capacity of an arc is more likely to be high if this arc is close to the root. We compute 5 instances for each different value of |V | selected (except for |V | = 20 and |V | = 25 because the number of vertices is too small): for each one we assign a different value of |T | selected in { 1 10 |V |, 10 |V |, 3 10 |V |, 6 10 |V |, |V | -1}.

Figure 2 .Figure 2 . 3 :

 223 Figure 2.3 deals with the cost of designing failure-resilient networks; the number of the

Figure 3 . 2 :

 32 Figure 3.2: Illustration of the construction of D G′ from G′ (the arc of length u ij corresponds to the standard dual arc)

Figure 3 . 3 :

 33 Figure 3.3: Construction of 2DG′ for the graph G′ of Figure3.1 .

  3 while T oBeRepaired do 4 Determine a maximum flow f in G ′′ + t and set H equal to G + t; 5 foreach a ∈ A ′ do 6 if (a ∈ A ′′ or f (a) = u a ) then remove a from H; 7 else set c H (a) = 0; 8 end 9 foreach a ∈ A \ A ′ do 10 if a has a tabu status then set c H (a) = c a + M ; 11 else set c H (a) = c a ; 12 end 13 for i = 1 to |T | -f r→t do 14 Compute a minimum cost path P (using c H ) linking r to t in H 15 foreach a ∈ P do 16 if a / ∈ A ′ then 17 Add a to A ′ ; 18 if u a > 1 then set c H (a) = 0 and f (a) = 1; a) < u a -1 then set f (a) = f (a) of TestSurvivability(A ′ ) is an arc set A ′′ then set G ′′ = (V, A ′ \ A ′′ );

25

  write the message "G = (V, A) is not k-survivable"Set A ′ = A,apply MakeMinimal(A ′ ) and set A * = A ′ ; 6 while no stopping criterion is met do 7 Generate a subset S A ′ of ⌈λ|A ′ |⌉ arcs in A ′ and set BestCost = +∞ (the arcs in S A ′ are the ⌈λ|A ′ |⌉ first arcs a of A ′ when the arcs of A ′ are sorted by decreasing value of ρ a c a ); 8 foreach a ∈ S A ′ do 9 Set S a A ′ = A ′ \ {a} and c a = c a + M ; a A ′ ) < BestCost then set BestCost = c(S a A ′ ) and a best = a; 13 Set c a = c a -M ; 14 end 15 Set A ′ = S a best A ′ and assign a tabu status to a best for τ iterations; 16 if c(A ′ ) < c(A * ) then set A * = A ′ ;

  which means that the Euclidian distance is multiplied by 0.8, 0.6, 0.4 or 0.2.Seven of these 60 instances did not pass the test of 1-survivability at the first line of Procedure TabuSearchCRkECSN. These instances therefore do not appear in our experiments. The tabu search was run 10 times on the 53 remaining instances and each execution was stopped after 45 seconds, while we have allocated 3000 seconds to each run of the exact methods described in Chapter 2. Based on preliminary experiments, we have used λ = 0.4 and τ = k = 1 appear in Table3.1. The |V | and |T | columns indicate respectively the number of vertices and terminals of each instance. Columns C opt and T opt indicate the cost of an optimal solution and the time (in seconds) needed by the exact method to find it, respectively. If no proof of optimality was obtained after 3000 seconds, we indicate the cost of the best feasible solution found as well as, in brackets, the best lower bound on the 3.4. COMPUTATIONAL EXPERIMENTS value of an optimal solution. Column C b indicates the best cost obtained after 10 runs of the tabu search, while column T b gives the best time needed to find such a solution, and column n b shows the number of runs for which a solution of that cost was found. Gray boxes in column C b mean that we could reach the proven optimal solution, while gray boxes in column n b indicate that the 10 runs of our tabu search all ended with the same cost. Column C a gives the average cost produced by our tabu search, over the 10 runs. While each run was stopped after 45 seconds, column T a indicates the average time at which the best solution A * was last improved (line 16 of Procedure TabuSearchCRkECSN).

  the exact method, and these optimal solutions were obtained for each of the 10 runs, except in one case: the instance with |V | = 45 vertices, |T | = 14 terminals and k = 2, where our tabu search has found the optimal solution in only 7 of the 10 runs. Again in this case, the average cost C a = 25.71 is very close to the optimal value C opt = 25.63 (which corresponds to an increase of around 0.3% of the cost). For these larger values of k, we see that TabuSearchCRkECSN is able, in 45 seconds, to get very big improvements when compared to the best solutions produced by the exact method in almost one hour. For example, for the instance with |V | = 100 vertices, |T | = 20 terminals and k = 3, the exact method stopped with a best upper bound equal to 54.79, while our tabu search has generated a solution of value C b = 35.82, and the average cost C a is equal to 36.43.

  order to introduce these constraints in the optimization model, we consider the Direct Current (DC) estimations of the load flow. If we consider the Direct Current Load Flow, it is customary to make the following assumptions [Seifi and Sadegh Sepasian 2011]: Assumption A Line resistances (inducing active power losses) are negligible i.e. H ≪ B, and we can assume that H vw = 0 for all [v, w] or equivalently that Y vw = ιB vw and |Y vw | = B vw . Notice that, since Y vw = |Y vw |(cos(δ vw ) + ι sin(δ vw )), the previous assumption implies cos(δ vw ) = 0 and thus we have δ vw ≈ π/2. Assumption B Voltage angle differences are small i.e. sin(θ v -θ w ) ≈ θ v -θ w and cos(θ v -θ w ) ≈ 1, for all v, w = 1, .., n. Assumption C Magnitudes of node voltages are equal to 1.0 per unit (flat voltage profile) i.e. |U v | = 1 for all v = 1, .., n.

r e 2 e 1 Figure 4

 14 Figure 4.1: A network buildt on a grid 4 × 3

(

  w) ∈ ⃗ E ρ ∈ L(θ, y) y ∈ {0, 1} |E|Q , θ ∈ [-ε, ε] |V | , ρ ≥ 0

(

  y) y ∈ {0, 1} |E|Q , θ ∈ [-ε, ε] |V ||E| , ρ ≥ 0 an arbitrary number of breakdowns, the number of variables and constraints becomes exponential: with k breakdowns, we would have to consider (|V ||E| k + |E|Q) variables before linearization and (Q| ⃗ E||E| k + |V ||E| k + |E|Q) after. Therefore we 4.3. ROBUST APPROACH end up with an intractable model to solve.

( 4 .

 4 13)-(4.15), i.e. we define those constraints only for ξ ∈ E S . We begin to solve the reduced problem (Lκ) E S . When a relevant integer feasible solution (ŷ, θ, ρ) is found, we solve a set of sub-problems (κ-sub) e with continuous variables. We define the set of edges selected in the current integer solution (ŷ, θ, ρ) ÊC = {e ∈ E | to the set of bi-directed arcs associated to ÊC . We define ÊS = E S ∩ ÊC corresponding to the intersection between the set of edges which are in the solution (ŷ, θ, ρ) and the set of edges for which the scenario of breakdown has been taken into account at this moment in the algorithm. Finally, we define: respectively ûvw ) corresponds to the susceptance (respectively capacity) on the cable built on[v, w]. For the integer feasible solution (ŷ, θ, ρ), we introduce the following sub-problem (κ-sub) e for each e ∈ ÊC \ ÊS :v,w]∈E C \{e} Bvw (θ v -θ w ) = P v ∀v ∈ V \ r Bvw (θ v -θ w ) ≤ ûvw ∀(v, w) ∈ ⃗ E C \ {e} θ ∈ [-ε, ε]

  polyhedron X (y, b) corresponds to the set of load flow and capacity constraints with penalty variables for a given value of y and b, i.e. once the network has been built

4 Wind farm cable layout optimization with constraints of load flow and robustness 4

  Nous proposons également un algorithme basé sur la génération de contraintes et donnons une méthode pour générer de meilleures contraintes à chaque itération de l'algorithme (la contrainte améliorée interdit plus de solutions entières non réalisables que la contrainte initiale). Nous montrons que la formulation à deux niveaux est une reformulation d'une autre formulation basée sur les coupes dans le graphe. Nous Nous utilisons une approximation du courant continu pour obtenir des équations linéaires. Ces équations sont ajoutées à un programme MIP (Mixed-Integer Program) et nous montrons que, lorsque ces contraintes sont satisfaites, les équations de load flow le sont et le réseau final est connecté. Nous donnons d'abord un MIP qui permet de résoudre le problème dans le cas non robuste (où nous ne considérons pas la possibilité de pannes sur les arcs). Dans un second temps, nous donnons un MIP pour le cas où k = 1 (une panne peut se produire) et un algorithme de génération de contraintes pour le résoudre. .1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Presentation of the problem . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 The Load Flow constraints . . . . . . . . . . . . . . . . . . . . . . .

	RÉSUMÉ LONG RÉSUMÉ LONG
	Contraintes (4a) et utilisons (LL) comme problème de séparation : si la valeur optimale de dualisé au deuxième niveau, il peut être intéressant d'étudier différentes façons de résoudre
	(LL) est inférieure à |T | pour la solution actuelle ŷ (solution entière de (BP) avec seule-cette formulation.
	ment un sous-ensemble de contraintes (4a) initialisées), nous générons des Contraintes (4a) Dans ce qui suit, nous résumons les principales contributions et esquissons quelques
	associées au point extrême dont les coordonnées sont les valeurs optimales de (b, λ, γ, µ, l) améliorations ou orientations de recherche pour l'avenir. Un autre aspect des cas réels qu'il pourrait être intéressant d'étudier est la stochasticité.
	en (LL). Les problèmes abordés dans cette thèse s'inspirent ou tournent autour du problème de Pour les parcs éoliens offshore de puissance équivalente, l'énergie produite par chaque
	la conception d'un réseau de câblage d'un parc éolien avec plusieurs notions de robustesse. éolienne est presque toujours la même, c'est pourquoi nous avons considéré une production
	d'énergie fixe à chaque éolienne. Cependant, la production réelle dépend en partie de la
	Cette thèse est issue d'un travail conjoint du Conservatoire National des Arts et Métiers
	(CNAM) de Paris, de l'ENSTA ParisTech et de Polytechnique Montréal, et aborde les prob-
	lématiques de conception des réseaux soumis à des ruptures de arcs après leur conception.

H, f (y) est supérieur à |T | (donc la valeur minimale de f (y) sur le polyèdre défini par les contraintes (4b)-(4e) est supérieur à |T |), ce qui signifie que la valeur d'un flot maximum ne peut devenir inférieure à |T |, même après toute décomposition k. Cependant, il existe un nombre exponentiel de Contraintes (4a). Pour résoudre ce problème, nous utilisons un algorithme de génération de contraintes où nous relâchons les Dans le chapitre 3, nous nous concentrons sur les graphes planaires pour le réseau de Steiner enraciné k-arc connecté avec contraintes de capacités. Nous présentons une méthode pour vérifier si un réseau est résilient ou non à la suppression d'un ensemble de k arcs en utilisant la dualité des graphes planaires et les problèmes de plus courts chemins. Nous proposons et décrivons un algorithme de recherche tabu dérivé de cette méthode. Nous testons notre algorithme et comparons son efficacité aux méthodes exactes présentées au chapitre 2. Dans le chapitre 4, nous étudions le problème réel de la conception d'un réseau de câblage de parc éolien avec des contraintes électriques de load flow. Nous expliquons l'étude du load flow, qui correspond à une analyse numérique du flux d'énergie électrique dans un système interconnecté. Nous devons nous assurer que l'énergie acheminée par chaque câble respecte les capacités électriques du câble en utilisant les équations de load flow pour analyser l'état du réseau électrique une fois le réseau construit. Comme l'analyse du load flow est un système non linéaire, nous utilisons une approximation afin de les inclure dans un programme linéaire à nombres entiers mixtes. Nous testons notre algorithme sur des données réelles et donnons des résultats numériques. Notre application principale étant la conception de réseaux de câblage de parcs éoliens, nous avons travaillé avec un ingénieur d'EDF dans le cadre d'un projet PGMO (Programme Gaspard Monge pour l'Optimisation, la recherche opérationnelle et leurs interactions avec RÉSUMÉ LONG les sciences des données) de la Fondation Mathématique Jacques Hadamard. Le développement durable étant aujourd'hui un objectif majeur, il apparaît important de se concentrer sur plusieurs problèmes concernant les énergies renouvelables, y compris la conception de tels réseaux de câblage. Dans le chapitre 1, nous nous concentrons sur la conception de réseaux d'arborescence (ou arbres enracinés). Dans ce contexte, les contraintes électriques peuvent être formulées comme des contraintes de flot classiques. Nous donnons un théorème de complexité et sa preuve qui dit que déterminer s'il y a un arbre de recouvrement enraciné, en respectant les contraintes de capacité (qui dit pour chaque arc (i, j) que le nombre de sommets dans le sous-arbre enraciné à j ne doit pas dépasser une valeur donnée u ij ), est un problème N P-Complet, même dans le cas des capacités uniformes. Ce résultat prolonge un résultat de Papadimitriou [Papadimitriou 1978], où un coût de sélection est associé à chaque arc du graphe, qui indique que déterminer s'il existe un arbre enraciné respectant les contraintes de capacité et sous un coût donné de sélection est N P-Complet. Nous étudions ensuite la conception des arborescences de Steiner avec différentes notions de robustesse : nous visons à concevoir des arborescences de Steiner en considérant le nombre de terminaux déconnectées de la racine après une suppression d'arc dans plusieurs scénarios. Pour autant que nous sachions, ce problème n'a pas été étudié dans la littérature. Nous donnons plusieurs formulations pour différents scénarios et les testons sur des données réelles de parcs éoliens afin d'évaluer leur impact sur le réseau conçu. Dans le chapitre 2, nous introduisons un problème appelé CRkECSN : nous visons à concevoir un réseau à coût minimum où nous pouvons acheminer une unité de flot de la racine à chaque terminal en respectant les capacités (une quantité limitée de flot peut RÉSUMÉ LONG être acheminée par chaque arc) même dans le cas de la suppression d'un sous-ensemble quelconque de k arcs dans le réseau construit (k étant un entier donné). Nous proposons plusieurs formulations, dont une nouvelle formulation bi-niveau, où le deuxième niveau est un problème minmax. considérons la possibilité de protéger les arcs ; ces arcs ne peuvent pas être supprimés des solutions. Nous donnons quelques résultats de test sur les instances générées et comparons les performances de nos algorithmes. Dans le chapitre 3, nous étudions également le CRkECSN, mais dans le cas des graphes planaires. Ceci est motivé par le fait que les parcs éoliens en mer peuvent souvent être modélisés par des graphes en grille. Le problème de déterminer si un graphe est k-survivable (c.-à-d. résilient à la suppression de tout sous-ensemble de k arcs) est NP-complet dans le cas général. Cependant, nous dérivons un théorème qui donne les propriétés sur le graphe dual planaire d'un graphe k-survivable et l'étendons pour résoudre ce problème en temps polynomial dans les graphes planaires, en déterminant une série de plus courts chemins. Les méthodes exactes pour le CRkECSN ne peuvent résoudre que des cas de taille relativement petite. Pour cette raison, nous décrivons également un algorithme de recherche tabu qui peut traiter des instances beaucoup plus grandes, à condition qu'elles soient planaires, et nous avons montré qu'il produit généralement des solutions optimales lorsque celles-ci sont connues. Notre algorithme a des temps de calcul très courts, ce qui le rend particulièrement intéressant dans la pratique, par exemple pour la conception de réseaux de collecte de parcs éoliens survivables avec des centaines d'éoliennes. Dans le chapitre 4, nous étudions le problème de la conception d'un réseau de câblage pour parcs éoliens offshore tout en respectant les équations de load flow. L'analyse du load flow correspond à un système non linéaire qui permet de déterminer l'état du réseau (calculs des tensions, puissances et courants de phase à chaque noeud ou câble du réseau), puis RÉSUMÉ LONG de s'assurer que la puissance acheminée par chaque câble est inférieure à sa capacité maximale. Nous testons ces MIP sur des données réelles fournies pour un parc éolien offshore. Enfin, nous donnons une formulation à deux niveaux conçue pour résoudre le problème pour des valeurs générales de k, et donnons des idées sur la façon de le résoudre efficacement. Le travail présenté dans cette thèse a donné lieu à plusieurs questions ou pistes de recherche intéressantes qu'il serait intéressant d'étudier dans l'avenir. Il apparaît que les contraintes électriques que nous avons étudiées sont plus faciles à prendre en compte lorsqu'on considère les réseaux arborescents. L'un des problèmes qu'il serait intéressant d'étudier est une version plus restreinte du CRkECSN, où nous voulons concevoir un réseau résilient à la suppression de tout sous-ensemble de k arcs et tel que le flot résultant doit être acheminé de la racine vers les terminaux par un sous-réseau arborescent (après suppression de ces k arcs). Nous avons commencé à étudier ce problème pour k = 1 sur des graphes de grille avec des contraintes de capacité uniformes et nous avons trouvé plusieurs propriétés pour des cas particuliers. Le problème semble plus difficile à résoudre que le CRkECSN, car la contrainte que le flot doit passer par un sous-réseau arborescent pour chaque scénario de suppression d'arc semble plus difficile à formuler que le CRkECSN. Nous pouvons également étudier le programme de bilevel proposé au chapitre 4. Cette formulation propose des défis intéressants. Les formulations de programmation à deux niveaux sont actuellement largement utilisées dans la littérature, et notre formulation pour le deuxième niveau en utilisant des variables d'écart a un nombre de variables inférieur à celui que nous avons testé dans cette thèse. Une fois que le problème min a été demande ou, dans les réseaux de parcs éoliens, de la quantité de vent, et il serait intéressant de prendre en compte cette incertitude. Contents Résumé long Introduction 0.1 General introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2.1 General notions in graph theory . . . . . . . . . . . . . . . . . . . . 0.2.2 Flows and networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2.3 Steiner trees and networks . . . . . . . . . . . . . . . . . . . . . . . . 0.3 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.3.1 Wind farm cable layout optimization . . . . . . . . . . . . . . . . . . 0.3.2 Steiner arborescence problems . . . . . . . . . . . . . . . . . . . . . . 0.3.3 Robust Steiner networks . . . . . . . . . . . . . . . . . . . . . . . . . 0.3.4 The k most vital arcs in flow networks and network interdiction problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Robust arborescences 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Definition of problems and complexity results . . . . . . . . . . . . . . . . . 1.3 Mathematical formulations and tests . . . . . . . . . . . . . . . . . . . . . . 2 Capacitated Rooted k-Edge Connected Steiner Network problem (CRkECSN) 67 CONTENTS 3.4 Computational Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The problem without breakdowns . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Mathematical formulation . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Variables and constraints . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Mathematical program . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Linearization of the program . . . . . . . . . . . . . . . . . . . . . . 4.3 Robust approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 The case k = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Bilevel formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Results analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  thesis, we have been in contact with EDF (Électricité de France),

	first producer and supplier of electricity in France, via PGMO (Programme Gaspard Monge
	pour l'Optimisation de la Fondation Mathématique Jacques Hadamard) and engineers
	working in the field of renewable energy networks. It appears that combinatorial and dis-
	crete aspects of those problems have been sparsely studied until now at EDF. Although the
	design of the cabling networks presents high economic stakes, robustness and resilience to
	breakdowns are important criteria too. Some work has also been done with the Canadian
	company Hatch, which led us to test our work on real data (we can underline that the

Minimum-Cost Steiner Tree Problem as

  S , E S ) such that |E S | = min{|E S ′ | | S ′ = (V S ′ , E S ′ ) is a Steiner tree spanning T in G}.Given a positive cost c e for each edge e ∈ E, we define similarly the the problem of finding a Steiner tree S = (V S , E S ) for which the sum of the costs c e ′ for e ′ ∈ E S is minimum. The Minimum-Cost Steiner Tree problem is N P-hard and generalizes both the Minimum Spanning Tree problem and the Shortest Path problem: if T = V , the Minimum Steiner Tree Problem is equivalent to the Minimum Spanning Tree Problem whereas if |T | = 2, it is equivalent to the Shortest Path problem.

	0.3. PREVIOUS WORK
	Minimum Steiner Tree Problem
	INSTANCE: A graph G = (V, E) and a set of terminals T ⊆ V .
	PROBLEM: Find a minimum Steiner tree spanning T in G. That is, find a Steiner tree
	S = (V
	E) and a subset of vertices T ⊆ V , a subgraph S of G is called a Steiner tree
	if S is a tree containing all vertices of T . A vertex t ∈ T is called a terminal vertex (or
	terminal) whereas a vertex v ∈ V \ T is called a Steiner vertex (or Steiner point). The
	minimum Steiner tree problem can be defined as follows:

  R 8 R 12 ∆ Crob ∆ Cbrob R BR *

	1.3. MATHEMATICAL FORMULATIONS AND TESTS
	Set |V| |E| |T| 1 91 220 42	Set R 1 21 35	29	0.18	0.56	21
	2 143 382 40	2 20 21	20	0.09	0.64	20
	3 220 510 88	3 22 32	30	0.24	0.33	22
	4 255 662 73	4 37 41	38	0.19	0.37	37
	(a) Data parameters	(b) Results on robust arborescences
	Table 1.1: Results on robust arborescences and data parameters

*

When trying to minimize the number of disconnected terminals in the worst case (see RCStA in Figure

1

.3), we have seen that the associated solutions have a reasonable cost, but the average robustness is not good, since the tree remains too deep. When finding the Balanced Steiner arborescence (see BRCStA in Figure

  For k ∈ N * , there are at least k+1 arc-disjoint paths between the root and each terminal in any feasible solution. Furthermore, any inclusion-wise minimal feasible solution induces at least a 2-edge-connected graph in the underlying undirected graph.

	Property 2.1.1

Proof:

The first part of the property is a consequence of Theorem 0.2.1 (

[START_REF] Menger | Zur allgemeinen kurventheorie[END_REF]

), in Subsection 0.2.1. Let G ′ be an inclusion-wise minimal feasible solution and assume that G ′ is not 2-edge-connected in the underlying undirected graph. Then there exists at least one edge e whose removal cuts G ′ into two parts. If the part that does not include the root contains terminals, then G ′ is clearly not a feasible solution because, if we remove e, then at least one terminal cannot be reached from the root. Otherwise, G ′ is not inclusion-wise minimal because, if we remove e, then the resulting graph is still a feasible solution. Hence, any inclusion-wise minimal feasible solution induces at least a 2-edge-connected graph. □ Remark 2.1.1 Property 2.1.1 implies that a necessary condition for the existence of a feasible solution is that there are at least k + 1 arc-disjoint paths between the root and each terminal in G. We assume without loss of generality that this is always verified in G, otherwise there is no feasible solution.

  1} |E| , there exists a solution where x is integer (see Theorem 0.2.3 in the Subsection 0.2.2 of the introduction), and hence there exists an optimal solution with x integer. The number of variables and constraints being exponential for arbitrary values of k, we propose a constraints-and-columns generation algorithm to solve the problem. We begin with a small subset of F. The separation problem is the problem of the k most vital links We use a procedure similar to the one used in Subsection 2.2.1: for small values of k, we compute a maximum s -t flow for each combination of k selected arcs of A I . If there is a combination of arcs whose deletion results in a maximum s -t flow lower than |T |, we add this arc-failure scenario, else the solution is feasible. If k is too big, we use the auxiliary MIP (CU T -SEP ), see Subsection 2.2.1.

	6a)
	(2.6b)
	(2.6c)
	(2.6d)

Constraints

(2.6a

) and

(2.6b

) ensure that there is a flow of value |T | for each arc-failure scenario F ∈ F, meaning that we can still route a unit of flow to each terminal after any k arc failures. Constraints (2.6c) ensure that the arc capacities are respected for each arc-failure scenario F ∈ F. Constraints (2.6d) ensure that, in each scenario F ∈ F, no flow is routed through deleted arcs. One can notice that the variable x must be an integer (because it corresponds to a number of terminals). However, we relax this integrality constraint. Indeed, for any value of y ∈ {0, 1} |E| , setting the value of x corresponds to routing a set of flows of value |T | on |F| different networks with integer capacities. Then, for any given value of y ∈ {0, in a flow network which is N P-hard [Ratliff, Sicilia, and Lubore 1975]: we search for the k arcs which, once simultaneously deleted, reduce the most the value of a maximum s -t 2.2. FORMULATIONS flow.

Table 2 .

 2

	1: Instance parameters

Table 2 .

 2 1 shows for each instance its number I, as well as the number of vertices

Table 2 .

 2 2: Results for non-uniform capacities, k = 1 and k ′ = 0 2.6. RESULTS ANALYSIS the optimal one. The algorithm associated with the cutset formulation finds the optimal solution for 39 instances out of 52 tested. For the other instances, the mean final gap is equal to 0.07. The algorithm associated with the flow formulation finds the optimal solutions for 27 instances out of 38 tested (all those instances have been optimally solved by the cutset formulation except Instance 38 which presents a final gap equal to 0.02). For the other instances, the mean final gap is equal to 0.13.

	2.6. RESULTS ANALYSIS
				Cutset				Flow
	I gap LR gap f time (s)	it nodes gap f time (s) it nodes
	1	0.15	0	0.4	13	0	0	0.1	2	32
	2	0.25	0	1.7	46	800	0	0.9 13	279
	3	0.28	0	5.8	113	4859	0	6.3 15	2237
	4	0.18	0	4.2	92	4423	0	6.2 20	1995
	5	0.19	0	3.0	61	554	0	1.4 14	273
	6	0.16	0	3.6	79	5194	0	9.5 12	2426
	7	0.24	0	8.8	127 19143	0	28.6 30	2290
	8	0.1	0	0.4	13	179	0	0.5	7	35
	9	0.2	0	5.7	106	4141	0	28.6 24	866
	10	0.21	0	8.8	126 11361	0	64.6 23	8408
	11	0.17	0	8.5	115 13161	0	41.3 16	7995
	12	0.07	0	0.5	13	13	0	0.38	4	13
	13	0.28	0	18.1	243 18441	0	87.4 26	3488
	14	0.25	0	10.0	143	8188	0	23.2 13	4070
	15	0.1	0	5.5	67	552	0	8.9 17	1316
	16	0.22	0	6.7	129	4318	0	20.8 15	1540
	17	0.17	0	6.4	93	3586	0	41.2 24	2961
	18	0.26	0	710	391 15.10 4	0	1947 34 35683
	19	0.15	0	13.6	116 20339	0	251 37	5016
	20	0.08	0	10.7	98	1964	0	9.16	5	1432
	21	0.16	0	3.4	70	601	0	4.9 11	363
	22	0.18	0	32.4	217 50927	0	384 16 28156
	23	0.19	0	19.6	149 21588	0	466 22	7129
	24	0.24	0	2050	766 57.10 4 0.09	3000 36 21610
	25	0.13	0	31.1	182 62060	0	353 20 22834
	26	0.28	0	21.2	188 24570	0	1642 27	8680
	27	0.21	0	1335	533 19.10 4	0.1	3000 34	8513
	28	0.29	0	20.0	155 22125	0	1812 29 12645
	29	0.08	0	8.6	66	1880	0	159.7 21	1431
	30	0.34	0	2950	557 14.10 4	0.3	3000 45	2015
	31	0.19	0	300.7	319 26.10 3 0.05	3000 29 32515
	32	0.24	0	130.0	301 16.10 3 0.09	3000 44	7547
	33	0.16	0	127.8	302 21.10 3 0.03	3000 38	5995
	34	0.33	0	223.6	369 20.10 3 0.15	3000 51	4065
	35	0.27	0	1102	667 10.10 4 0.26	3000 56	937
	36	0.17	0	73.1	304 65183 0.12	3000 49	2057
	37	0.16	0	791.4	386 13.10 4 0.12	3000 50	2234
	38	0.13 0.02	3000	580 99.10 4 0.13	3000 55	1458
	39	0.18	0	245.3	436 16.10 3	-	-	-	-
	40	0.27 0.09	3000	939 19.10 4	-	-	-	-
	41	0.17 0.03	3000 1050 35.10 4	-	-	-	-
	42	0.1 0.02	3000	827 59.10 4	-	-	-	-
	43	0.32 0.18	3000	928 11.10 4	-	-	-	-
	44	0.25 0.11	3000	957 11.10 4	-	-	-	-
	45	0.26 0.15	3000 1142 12.10 4	-	-	-	-
	46	0.17 0.08	3000 1227 30.10 4	-	-	-	-
	47	0.1 0.01	3000	799 77.10 4	-	-	-	-
	48	0.27	0.1	3000 1155 10.10 4	-	-	-	-
	49	0.26	0.1	3000	909 10.10 4	-	-	-	-
	50	0.26 0.12	3000 1190 12.10 4	-	-	-	-
	51	0.13	0	964.2	558 89.10 3	-	-	-	-
	52	0.12 0.01	3000	672 80.10 4	-	-	-	-

Table 2 .

 2

4: Results for non-uniform capacities, k = 3 and k ′ = 0 on instances with non-uniform capacities. The columns are defined similarly to the ones in Table

Table 2 .

 2 2.6. RESULTS ANALYSISwe remove from the table those instances. Similarly to the previous results for k ∈ {1, 2}, the cutset formulation is more efficient. Furthermore, the number of constraints generated in the flow formulation is closer to the one of the cutset formulation than in k ∈ {1, 2}.

				Cutset			Flow
	I k' gap LR gap f time(s)	it	n gap f time (s) it	n
	1-10 1	0.24	0.0	5.0	92	6941	0.0	25.9 17	2826
	-2	0.27	0.0	7.9	114 12897	0.0	59.1 29	3017
	-3	0.3	0.0	11.1	125 20934	0.0	66.4 31	4052
	11-20 1	0.23	0.0	12.0	141 13319	0.0	201 35	3734
	-2	0.25	0.0	16.0	158 19726	0.0	337 41	5099
	-3	0.28	0.0	24.2	182 40042	0.0	642 52	7656
	21-30 1	0.22 0.01	727	346	8.10 4 0.07	2308 38 11728
	-2	0.24 0.01	937	388	9.10 4 0.06	2290 47	7198
	-3	0.26 0.02	945	424	9.10 4 0.08	2561 55	8795
	31-40 1	0.26 0.01	952	402	5.10 4 0.19	2740 46	3764
	-2	0.28 0.01	1207	494	7.10 4 0.23	3000 58	3514
	-3	0.3 0.02	1321	531	6.10 4 0.23	3000 62	2532
	41-50 1	0.24 0.08	2176	818 11.10 4	-	-	-	-
	-2	0.27	0.1	2590	932 13.10 4	-	-	-	-
	-3	0.29 0.13	2755 1028 14.10 4	-	-	-	-
	51-58 1	0.2	0.1	3000 1237 17.10 4	-	-	-	-
	-2	0.23 0.14	3000 1564 14.10 4	-	-	-	-
	-3	0.24 0.15	3000 1466 15.10 4	-	-	-	-

5: Results for non-uniform capacities, k = 1 and k ′ ∈ {1, 2, 3} Tables 2.5, 2.6 and 2.7 present results for our problem with the possibility of protecting some arcs. In real applications, protecting an arc can correspond to double the cable or adding devices protecting the cables against the environment (like extreme cold). Since those modifications can be expensive, we only consider small values of k ′ .

Table 2 .

 2 5 presents the results of the cutset and flow formulations for k = 1 and k ′ ∈ {1, 2, 3} on instances with non-uniform capacities. The column I gives the set of the instances on which the formulation is tested, the column gap LR gives the mean value of the gap between the optimal value of the continuous relaxation and the optimal value of the integer formulation for each instance of the data set tested. For each formulation, the column gap f gives the mean value of the final gap of each instance of the data sets between the best lower bound and the best integer solution found (if the gap is equal

	2.6. RESULTS ANALYSIS
				Cutset			Flow
	I k' gap LR gap f time (s)	it	n gap f time (s) it	n
	1-10 1	0.14	0.0	7.5	108	9088	0.0	384 48	7971
	-2	0.2	0.0	14.6	152	21575 0.02	1047 64 10902
	-3	0.22	0.0	28.2	190	53192 0.05	1238 78 14521
	11-20 1	0.19	0.0	18.7	167	17192 0.04	1818 69 11621
	-2	0.22	0.0	37.7	261	42657 0.12	2598 86 14564
	-3	0.24	0.0	80.4	291	100650 0.15	2533 98 12030
	21-30 1	0.17	0.0	450	397	590660	-	-	-	-
	-2	0.19	0.0	606	491	829507	-	-	-	-
	-3	0.22 0.02	1066	531 1148662	-	-	-	-
	31-40 1	0.23 0.02	1275	699	856019	-	-	-	-
	-2	0.26 0.06	1514	746	726194	-	-	-	-
	-3	0.28 0.08	1592	797	796008	-	-	-	-
	41-50 1	0.2 0.08	1719	908 1298931	-	-	-	-
	-2	0.23	0.1	1909 1113	902446	-	-	-	-
	-3	0.3 0.16	2503 1367 1295592	-	-	-	-
	51-58 1	0.23 0.05	1842	929	733356	-	-	-	-
	-2	0.24 0.07	1924 1209	944623	-	-	-	-
	-3	0.3	0.1	2632 1406 1343762	-	-	-	-

Table 2

 2

.6: Results for non-uniform capacities, k = 2 and k ′ ∈ {1, 2, 3}

Table 2 .

 2

				Cutset			Flow
	I k' gap LR gap f time	it	n gap f time	it	n
	1-10 1	0.14	0.0 16.7	234	9584 0.08 1835 114 4384
	-2	0.21	0.0 16.6	186	25975 0.06 1910 132 3757
	-3	0.23	0.0 29.9	221	53703 0.15 1992 136 3948
	11-20 1	0.21	0.0	117	372	108708 0.13 3000	66	588
	-2	0.21	0.0	234	359	247729 0.18 3000	90	914
	-3	0.3 0.01	472	503	340496 0.25 2869	76 1413
	21-30 1	0.16	0.0	149	364	272985	-	-	-	-
	-2	0.28 0.02 1078	715 1182379	-	-	-	-
	-3	0.3 0.03	990	827	678130	-	-	-	-
	31-40 1	0.31 0.07 1843 1127 1038762	-	-	-	-
	-2	0.36 0.11 2021 1392	994130	-	-	-	-
	-3	0.37 0.14 2049 1512	975210	-	-	-	-
	41-50 1	0.31 0.08 3000 1580 1950209	-	-	-	-
	-2	0.27 0.11 2430 1683	824006	-	-	-	-
	-3	0.35 0.21 2451 2246	680713	-	-	-	-
	51-58 2	0.26	0.0 1174	350 1189524	-	-	-	-
	-3	0.36	0.0 2150	674 1156240	-	-	-	-

7: Results for non-uniform capacities, k = 3 and k ′ ∈ {1, 2, 3}

Table 2 .

 2 7 presents the results of the cutset and flow formulations for k = 3 and k ′ ∈ {1, 2, 3} on instances with non-uniform capacities; the columns are similar to the ones in Table2.5. Similar remarks as the ones of Table2.6 can be made: the flow formulation is much slower when k = 3 whereas the cutset formulation is not as much impacted by the incrementation of k.

Table 2 .

 2 8 presents the results of the cutset formulations for k = 1 and k ′ = 0 on in-

	2.6. RESULTS ANALYSIS
		Uniform-Cutset	Regular-Cutset
	I time(s) it	nb n time(s)	it	nb n
	1	0.07	2	0	0.11	4
	2	0.28	6	2	0.65	28
	3	4.98 32 1215	5.39	44
	4	0.24	5	0	0.32	9
	5	0.36	8	0	0.9	29
	6	0.44 10	46	0.64	22
	7	0.43	8	0	1.1	28
	8	0.28	3	0	0.37	7
	9	0.25	5	28	0.31	11
	10	0.59 14	23	1.02	32
	11	0.39	8	0	0.89	24
	12	0.61 11	21	1.44	36
	13	0.46	7	1	0.87	16
	14	0.23	5	0	0.34	10
	15	0.35	5	0	0.51	15
	16	0.54	9	32	1.96	45
	17	0.74 10	0	2.01	37
	18	0.36	4	0	0.33	5
	19	0.53	8	208	1.11	30
	20	0.36	5	3	0.6	13
	21	0.72 10	55	1.47	28
	22	1.2 14	124	2.78	41
	23	0.55	5	2	0.82	11
	24	0.36	5	2	0.57	15
	25	0.7	8	118	1.12	19
	26	1.62 17	276	3.58	49
	27	2.55 24	146	7.19	81
	28	1.42 11	4	1.83	17
	29	1.39 17	589	3.34	57
	30	2.07 21	853	5.4	71
	31	1.2 12	12	4.81	59
	32	0.54	4	0	0.87	8
	33	2.65 15	33	4.3	29
	34	3.25 33 1009	8.79	86
	35	1.42 13	185	2.07	24
	36	3.78 31	642	10.37	95
	37	3.32 19	111	7.2	48
	38	2.38	9	50	3.41	17
	39	2.98 27 1273	7.8	88
	40	3.14 25	406	6.57	60
	41	3.22 22	709	6.82	60
	42	1.27	5	19	2.74	15
	43	3.76 12	112	12.69	52
	44	6.39 43 2325	25.06 140
	45	5.85 40 1772	13.56	92
	46	7.76 36 1409	16.07	84
	47	6.32 25	217	10.25	45
	48	8.47 26	481	34.09 113
	49	11.72 56 5350	76.47 134
	50	10.18 37 1244	24.34 127
	51	12.99 51 2975	65.37 181
	52	15.06 40 1247	33.08	99
	53	13.43 20	198	26.14	46

stances with uniform capacities. We compute the tests on the Regular-Cutset formulation (which corresponds to the classic cutset formulation proposed in Equation (2.2) in Sub-

Table 2 .

 2 8: Results for uniform capacities and k = 1 2.6. RESULTS ANALYSIS section 2.2.1) and the Uniform-Cutset formulation (which corresponds to the modification of the formulation to reduce the number of constraints in the case of uniform capacities, see Equation(2.5) in Subsection 2.2.1). For each instance, we test the formulations when uniform capacities are equal to 0.4|T |, 0.6|T | and 0.8|T |. Column I gives the instance on which the formulations are tested; column time gives the solving time of the instance for each formulation; column it gives the number of iterations of the constraints generation algorithm for the instance for each formulation; column nb n gives the number of nodes generated for the instance for each formulation. We did not give the final gap since each instance has been optimally solved by both formulations within the 3000 seconds given to the algorithms.

Table 2 .

 2 10 presents the results obtained with the Regular-Cutset and Uniform-Cutset

	2.6. RESULTS ANALYSIS
		Uniform-Cutset	Regular-Cutset
	I time(s)	it	nb n time(s)	it	nb n
	1	0.31	7	5	0.65	20
	2	0.33	8	6	1.27	44
	5	0.49	10	61	2.02	56
	6	0.84	16	134	2.69	68
	7	0.77	11	10	1.51	34
	9	0.28	4	2	1.14	30
	10	1.44	26	111	5.25 106
	11	0.82	14	0	3.58	71
	16	0.68	9	19	2.94	52
	19	1.44	22	859	6.85 116
	20	3.25	34	1310	8.77 108
	21	2.6	31	463	8.97 121
	22	2.19	16	99	5.06	47
	23	0.73	4	1	0.85	8
	24	0.97	16	85	4.4	85
	25	3.84	43	567	9.56 120
	26	2.59	22	228	11.56 111
	28	0.85	4	0	0.77	6
	29	3.86	42	2783	37.0 260
	30	7.09	68	2328	33.25 236
	31	4.73	39	1338	38.18 233
	32	1.55	7	24	1.59	11
	33	0.41	1	0	0.36	2
	34	30.24	85 43667 2720.92 645
	36	6.79	42	2504	34.65 189
	37	4.27	19	150	28.48 132
	38	1.96	6	0	2.59	10
	39	4.95	43	1789	40.9 276
	40	14.27	78	7095	198.69 344
	41	6.79	36	505	16.62 102
	42	8.03	27	1210	25.26	97
	43	3.81	9	94	5.0	15
	44	50.38 118 73169 2656.92 744
	49	68.69 110 65440 1536.17 421
	50	59.39 108 90681 1450.07 460
	51	46.41 108 27507 2678.41 533
	52	37.85	67	6070	222.36 270
	53	17.27	23	1214	30.83	55
	Table 2.9: Results for uniform capacities and k = 2

Table 2

 2

	2.6. RESULTS ANALYSIS
		Uniform-Cutset	Regular-Cutset
	I time(s) it	nb n time(s)	it	nb n
	1	0.19	5	0	0.46	13	0
	6	0.74	9	18	1.72	36	184
	7	0.43	3	0	0.66	8	0
	9	0.66	7	0	2.42	53	711
	16	0.77	9	5	4.32	58	495
	19	1.88 21	220	8.51 115	3565
	20	0.79	6	0	6.71	68	575
	24	0.75	9	0	3.63	55	428
	34	14.39 73 3669	594.06 635 720890
	39	7.91 45 1692	71.66 349	48393
	40	11.37 39	593	87.91 320	28594
	44	16.17 66 1635	197.38 581 108704
	49	38.66 76 5924	644.54 553 358451

.10: Results for uniform capacities and k = 3

  and to then order the arcs by non-increasing values of c ′ a . In Procedure MakeMinimal, at each iteration on an arc (i, j) ∈ A ′ , if P has a negative length, it means that there is a set of k arcs

	Remark 3.3.1

  with |T | ∈ {⌈0.1|V |⌉ , ⌈0.2|V |⌉ , ⌈0.3|V |⌉ , ⌈0.6|V |⌉ , |V | -1} terminals. To create them, we have generated |V | random vertices in the Euclidean plane 3.4. COMPUTATIONAL EXPERIMENTS [0, 1] × [0, 1], and the edges are those of a Delauney triangulation. One vertex, chosenat random, is defined as the root r, while |T | other vertices, chosen at random, are considered as terminals. This gives a total of 60 undirected planar graphs. To get oriented graphs, we have replaced every edge linking two vertices i and j by two arcs (i, j) and (j, i).Since arcs that are close to the root r typically require larger capacities than the other ones, the capacity u ij of an arc (i, j) is chosen at random in {⌈0.8|T |⌉ , ⌈0.6|T |⌉} if there is a path with at most 2 arcs linking r to i, and in {⌈0.8|T |⌉ , ⌈0.6|T |⌉ , ⌈0.4|T |⌉ , ⌈0.2|T |⌉} otherwise. According to our experiments, these capacities are high enough to ensure, in most cases, the existence of a 1-survivable subgraph, but are also low enough to make the CRkECSN instances difficult to solve.

Table 3 .

 3

	3.4. COMPUTATIONAL EXPERIMENTS
	|V|	|T|	C opt	T opt	C b	T b	n b	C a	T a	I a
	20	4	15.23	1.0	15.23	0.0	10	15.23	0.1	4929
	20	6	20.93	5.6	20.93	0.0	10	20.93	0.1	2069
	25	8	22.03	17.6	22.03	0.2	10	22.03	0.9	1309
	25	15	26.49	94.6	26.49	0.4	10	26.49	1.1	616
	30	9	19.46	17.1	19.46	0.2	10	19.46	1.6	1021
	35	10	23.06	38.6	23.06	1.2	10	23.06	2.7	567
	40	4	16.59	154.2	16.59	0.2	10	16.59	1.3	914
	40	12	29.05	894.4	29.05	2.5	10	29.05	6.8	257
	40	39	35.57	13.3	35.57	2.1	10	35.57	15.4	119
	45	4	12.69	164.9	12.69	0.8	10	12.69	2.3	703
	45	9	19.00	1425.4	19.00	0.5	10	19.00	4.1	327
	45	14	25.63	138.2	25.63	5.9	7	25.71	15.0	175
	50	5	17.56	991.7	17.56	2.2	10	17.56	5.5	338
	50	10	28.57 (19.43)	3000	25.53	6.5	6	25.57	12.2	139
	50	15	23.95 (22.27)	3000	23.33	2.0	10	23.33	7.0	177
	60	6	25.72 (16.98)	3000	23.25	11.0	3	23.31	25.2	142
	60	18	29.29 (21.97)	3000	26.92	17.4	7	26.92	28.1	100
	60	36	40.59 (35.31)	3000	39.29	24.6	2	39.55	32.6	52
	70	7	21.19 (10.81)	3000	17.59	3.9	9	17.60	23.7	189
	70	14	33.25 (16.96)	3000	27.05	9.1	3	27.16	24.3	74
	80	8	26.17 (12.56)	3000	18.84	11.1	8	18.86	21.8	89
	90	9	41.56 (12.47)	3000	25.10	23.6	7	25.12	30.9	59
	90	18	38.52 (11.56)	3000	28.05	29.0	1	28.40	36.1	47
	90	27	47.35 (10.42)	3000	34.85	34.5	1	35.38	40.4	38
	90	54	51.67 (10.85)	3000	41.16	41.5	1	41.79	41.3	22
	90	89	52.89 (29.09)	3000	51.03	42.8	1	52.35	43.2	17
	100	10	36.55 (12.06)	3000	23.29	15.1	1	23.64	33.6	47
	100	20	39.24 (11.77)	3000	25.37	29.5	1	25.51	30.3	48
	100	30	42.82 (11.99)	3000	32.04	39.6	1	32.80	39.7	31
	100	60	50.52 (14.65)	3000	40.51	44.3	1	41.82	42.9	22
	100	99	53.51 (26.76)	3000	51.02	45	1	52.55	44.6	16

1: Results for k = 1 where (i, j) ∈ A if and only if (j, i) ∈ A.

Table 3 . 2

 32

	|V|	|T|	C opt	T opt	C b	T b	n b	C a	T a	I a
	35	10	34.76	42.4	34.76	1.2	10	34.76	3.2	320
	40	4	23.51	356.1	23.51	0.9	10	23.51	3.6	423
	45	4	18.64	335.1	18.64	1.0	10	18.64	2.4	335
	60	6	35.78 (22.18)	3000	32.83	7.0	9	32.89	19.0	95
	70	7	29.54 (15.36)	3000	25.96	14.9	3	26.03	17.1	74
	70	14	44.53 (23.60)	3000	37.93	13.8	3	37.99	22.8	53
	100	10	42.54 (15.31)	3000	32.12	38.8	2	32.60	40.7	27
	100	20	54.79 (15.89)	3000	35.82	36.9	1	36.43	39.8	24

: Results for k = 2 where (i, j) ∈ A if and only if (j, i) ∈ A.

Table 3 .

 3

	3.4. COMPUTATIONAL EXPERIMENTS
	|V|	|T|	C opt	T opt	C b	T b	n b	C a	T a	I a
	20	4	12.63	11.5	12.63	0.0	10	12.63	0.0
	20	6	17.48	9.4	17.48	0.1	10	17.48	0.3
	20	12	24.94	16.0	24.94	0.0	10	24.94	1.6
	20	19	42.57	11.3	42.57	0.0	10	42.57	0.1
	25	5	14.33	20.8	14.33	0.0	10	14.33	0.1
	25	8	20.45	28.2	20.45	0.0	10	20.45	0.5
	25	15	24.24	21.9	24.24	0.3	10	24.24	0.7
	30	3	8.61	2.3	8.61	0.0	10	8.61	0.0
	30	9	20.18	77.0	20.18	0.3	10	20.18	0.9
	30	18	30.40	23.5	30.40	0.1	10	30.40	0.4
	30	29	41.76	20.0	41.76	0.3	10	41.76	0.8
	35	4	9.03	10.2	9.03	0.1	10	9.03	0.2
	35	7	20.76	32.2	20.76	0.2	10	20.76	0.4
	35	10	24.68 (22.46)	3000	24.07	0.4	10	24.07	3.7
	35	34	50.56	57.2	50.56	1.2	3	50.56	1.6
	40	4	13.28	116.2	13.28	0.1	10	13.28	0.9
	40	8	25.23	199.9	25.23	0.3	10	25.23	0.8
	40	12	26.82	850.1	26.82	1.1	4	26.83	1.3
	40	24	31.97	120.3	31.97	1.5	10	31.97	2.3
	40	39	55.09	62.0	55.09	3.0	10	55.09	4.6
	45	4	9.06	78.0	9.06	0.2	10	9.06	1.2
	45	9	18.14	241.3	18.14	0.8	10	18.14	1.7
	45	14	26.20	440.5	26.20	5.4	10	26.20	10.9
	45	27	44.85	162.6	44.85	2.3	10	44.85	4.1
	45	44	59.17	126.8	59.17	5.5	10	59.17	8.6
	50	5	13.87	373.5	13.87	0.1	10	13.87	1.1
	50	10	25.40 (21.34)	3000	24.93	1.4	8	24.93	11.8
	50	15	26.9 (19.37)	3000	25.85	2.3	7	25.96	3.4
	50	30	37.74	183.3	37.74	2.5	10	37.74	6.2
	60	6	24.75 (13.12)	3000	21.73	8.4	9	21.74	17.4
	60	12	29.93 (26.64)	3000	29.41	5.0	2	29.53	9.1
	60	18	32.33 (17.13)	3000	29.91	8.1	5	29.93	18.2
	60	36	44.04	2487.4	44.04	14.3	7	44.06	25.6
	70	7	19.03 (10.85)	3000	16.93	1.9	10	16.93	10.1
	70	14	35.52 (7.81)	3000	28.71	19.7	3	28.79	29.4
	70	21	34.28 (24.00)	3000	32.18	9.9	8	32.19	15.8
	70	42	54.11 (45.45)	3000	52.23	19.6	1	52.45	24.6
	70	69	64.24	731.2	64.24	35.6	2	64.32	39.1
	80	8	20.51 (11.69)	3000	17.04	5.0	6	17.06	18.8
	80	16	33.52 (5.36)	3000	26.20	22.0	1	26.75	16.6
	80	24	45.90 (30.29)	3000	39.77	16.1	1	40.49	21.2
	80	48	49.84 (38.38)	3000	48.61	39.6	1	48.77	37.5
	80	79	65.31 (64.00)	3000	65.76	44.1	1	66.58	42.4
	90	9	30.81 (8.32)	3000	23.40	9.7	2	23.51	27.8
	90	18	41.73 (12.94)	3000	32.29	38.1	1	32.67	32.2
	90	27	44.92 (17.07)	3000	38.07	26.9	1	38.43	34.0
	90	54	51.14 (32.73)	3000	48.83	41.1	1	49.68	41.3
	90	89	73.08 (73.08)	3000	73.94	40.7	1	74.92	42.4
	100	10	24.27 (9.71)	3000	21.84	11.4	3	22.00	24.8
	100	20	35.93 (8.98)	3000	27.38	34.3	1	27.71	30.9
	100	30	46.31 (12.97)	3000	36.78	33.7	1	37.55	39.9
	100	60	57.19 (37.17)	3000	56.38	40.5	1	57.12	42.7
	100	99	75.05 (70.55)	3000	76.98	45	1	78.03	44.1

3: Results for k = 3 where (i, j) ∈ A if and only if (j, i) ∈ A.

Table 3 .

 3

	3.4. COMPUTATIONAL EXPERIMENTS
	|V|	|T|	C opt	T opt	C b	T b	n b	C a	T a	I a
		4	26.99	15.8	26.99	0.1	10	26.99	1.8	2084
		6	29.39	5.9	29.39	0.0	10	29.39	0.0	1343
		8	34.98	12.0	34.98	0.0	10	34.98	0.1	817
		15	47.06	18.9	47.06	0.0	10	47.06	0.1	425
		9	35.88	46.5	35.88	0.4	10	35.88	0.7	451
		10	41.52 (38.61)	3000	41.34	1.0	4	41.34	2.6	292
		4	21.51	515.6	21.51	0.5	10	21.51	1.2	749
		12	43.32	75.0	43.32	1.6	4	43.43	5.7	216
		4	17.40 (17.23)	3000	17.40	0.5	10	17.40	2.2	527
		9	35.64	281.2	35.64	1.9	10	35.64	3.3	222
		14	47.78	190.5	47.78	2.8	8	47.78	13.9	179
		5	24.84	2313.6	24.84	1.0	10	24.84	3.4	325
		10	43.90 (38.19)	3000	41.97	2.9	9	42.04	8.6	181
		6	38.68 (17.79)	3000	33.81	12.2	1	33.91	19.2	124
		18	52.55 (50.97)	3000	52.23	9.0	10	52.23	18.2	99
		36	85.78	438.2	85.78	10.4	6	85.80	21.9	51
		7	32.38 (18.46)	3000	29.82	6.8	4	29.93	11.8	119
		14	56.24 (9.56)	3000	47.52	16.6	2	47.66	27.7	71
		8	33.42 (19.38)	3000	29.58	7.1	7	29.63	15.2	84
		18	61.59 (22.79)	3000	51.37	33.9	1	51.83	38.7	45
		27	71.56 (46.51)	3000	68.61	40.8	1	68.94	41.8	36
		54	93.78	1983.3	94.05	42.4	2	94.25	41.4	25
		10	52.01 (12.48)	3000	36.29	34.6	1	36.94	37.3	36
		20	58.46 (6.43)	3000	44.51	41.6	1	45.06	41.4	28
		30	77.10 (40.09)	3000	65.17	43.1	1	65.55	43.3	19
		60	106.62 (105.55)	3000	106.45	44.9	1	107.35	44.3	10

4: Results for k = 1 where (i, j) / ∈ A if (j, i) ∈ A.

Table 3 .

 3

	V	T	C opt	T opt	C b	T b	n b	C a	T a	I a
		10	55.91	121.8	55.91	18.8	1	56.92	16.5	222
		4	33.59	988.4	33.59	1.0	9	33.64	11.2	379
		4	28.54	2165.7	28.54	0.6	10	28.54	1.8	311
		6	52.69 (32.67)	3000	49.12	13.2	1	49.24	12.8	109
			Table 3.6: Results for k = 3 where (i, j) / ∈ A if (j, i) ∈ A.

5: Results for k = 2 where (i, j) / ∈ A if (j, i) ∈ A.

  • Q v : the net reactive power injection in MVAr (Mega Volt Ampere reactive), which is the difference between reactive power generation and reactive power demand at node v • U v : the voltage magnitude in pu (per unit) at node v • θ v : the voltage angle in radians at node v.

	4.1. INTRODUCTION
	I = Y U	(4.1)
	We can apply Kirchhoff's law (see Chapter 2.4 in [Alexander and Sadiku 2009]) to
	each node, which results in:

  |Y vw |e ιδvw = H vw + ιB vw = |Y vw | cos δ vw + ι|Y vw | sin δ vw where H vw and B vw are respectively called conductance and susceptance at [v, w], and where δ vw is the argument of Y vw . Using (4.1) and (4.2), one can derive with some calculations the so-called Load Flow equations (see Appendix A in [Seifi and Sadegh Sepasian 2011]) for each node v = 1, .., n :

the vth element of U . Using (4.1) and (4.2), we have: P v -ιQ v |U v | e ιθv = n ∑ w=1 Y vw U w The Y matrix is symmetrical. The diagonal elements Y vv of Y (self admittance of node v) are equal to the sum of admittances of all nodes w connected to v. The off diagonal elements Y vw (mutual admittance) are equal to the negative sum of the admittances between v and w, and we have Y vw = Y wv =

  ′ is not connected to 4.2. THE PROBLEM WITHOUT BREAKDOWNS the root node r. Let G(v ′ ) = (V ′ , E ′ ) be an inclusion-wise maximal connected subgraph of G that contains v ′ . By assumptions r / ∈ V ′ . Let us consider the sum

	S =	∑	P v
		v∈V ′
	4.1.1 If the load flow equations 4.5 are satisfied at each node of a subgraph
	Ĝ = (V, Ê) of G = (V, E), with Ê ⊆ E and B vw set to 0 if no cable is built on the edge
	[v, w] (i.e. [v, w] / ∈ Ê), then there exists a chain in Ĝ between each node v producing a

positive active power flow (i.e. such that P v > 0) and the root.

Proof: Assume that there exists v ′ ∈ V such that P v ′ > 0 and v

else set T oBeRepaired = f alse;

end

3.4. COMPUTATIONAL EXPERIMENTS

Remerciements

Introduction

In this chapter, we focus on the design of networks which are resilient to one or several breakdowns, studying the Capacitated Rooted k-Edge Connected Steiner Network Problem (CRkECSN) defined in Chapter 2 in the case of planar networks. We recall that G = (V, A) is a directed input graph, that c and u are respectively a cost and a capacity function on A, and that r and |T | are respectively the root and the terminals. We say that G has a feasible flow if it is possible to route one unit of flow from the root to each terminal while respecting the arc capacity constraints. Given an integer k ≥ 0, a subgraph

at most k arcs of A ′ has a feasible flow. We aim at selecting a minimum cost subset

In this chapter, we focus on planar graphs which are useful in practice since many underlying graphs in real-world networks are planar. In the next section, we describe a procedure that determines in polynomial time whether a given planar graph is k-survivable.

In Section 3.3, we embed this procedure into a tabu search. Computational experiments 3.3. TABU SEARCH flow reaching t 1 can then only come from vertex u.

Theorem 3.2.1 provides an easy way to test k-survivability. Indeed, it is sufficient to determine all shortest paths in (k + 1)D G′ linking a first to a (k + 1)-th copy of a vertex. If one of these paths has a strictly negative length, then the second part of the proof of Theorem 3.2.1 provides a procedure to determine a set A ′′ of at most k arcs whose removal transforms G ′ into a graph with no feasible flow. This is summarized in Procedure TestSurvivability which, given an arc set A ′ , either determines a subset

Tabu Search

As shown in [START_REF] Bentz | On the edge capacitated Steiner tree problem[END_REF], CRkECSN is NP-hard, and exact methods can only solve instances of relatively small size. This justifies the use of metaheuristics

A repair procedure

In what follows, we denote by c a the cost of arc a in the input graph G, and by G ′ + t the graph obtained from a subgraph G ′ of G by adding a sink t to which all terminals are linked. Let G ′ = (V, A ′ ) be a subgraph of G which has to be repaired in order to become ksurvivable. We use the TestSurvivability procedure in order to determine a subset

G with no feasible flow. We then determine a maximum flow f in G ′′ + t . This maximum flow has a value f r→t strictly smaller than |T | (since it is not feasible). In the next step, we build a graph H from G + t as follows:

• all arcs a ∈ A ′ \ A ′′ for which the flow f (a) is equal to the capacity u a of a (i.e. saturated arcs) are removed from H; the other arcs of A ′ \ A ′′ are kept in H, but with a zero cost c H (a) = 0. This can be explained by the fact that we do not reroute existing and non-deleted flow, the repair procedure increases the existing flow.

• all arcs a ∈ A \ A ′ are kept in H. Those with no tabu status have their original cost c H (a) = c a , while the others have a cost c H (a) = c a + M , where M is an integer greater than the total cost of the arcs in G.

• all arcs a linking a terminal to the sink t are kept in H and have cost c H (a) = 0.

We next determine a path P of minimum cost linking r to t in H, using cost function c H . Every arc a on P which does not belong to A ′ is added to G ′ , which means that by sending one unit of flow on P , the value of the new flow in G ′′ + t (where

uses the updated arc set A ′ ) is exactly one unit larger than the previous one. The idea behind the definition of cost function c H is to only pay for the addition of arcs not in A ′ :

if an arc a ∈ A \ A ′ has no tabu status, then the cost of its addition is its original cost c a , while a penalty M is added to c a if a has a tabu status (the arc is then only added if it is necessary for the solution to be feasible, otherwise its cost is too high to be selected).

We repeat this process until we get a flow of In the following we sum up the main contributions and we outline some future improvements or research directions.

Main contributions

The problems addressed in this thesis take inspiration or revolve around the problem of designing a cabling network of a wind farm with several notions of robustness. Sustainable development being a major goal nowadays, it appears important to focus on several problems concerning renewable energies, including the design of such cabling networks.

In Chapter 1, we focus on the design of arborescence (or rooted tree) networks. In this context, electricity constraints can be formulated as classical flow constraints. We give a complexity theorem and its proof which states that determining whether there is a rooted spanning tree, respecting the capacity constraints (which states for each arc (i, j) that CONCLUSION the number of vertices in the subtree rooted at j must not exceed a given value u ij ), is N P-Complete, even in the case of uniform capacities. This results extends a result from

Papadimitriou [START_REF] Papadimitriou | The complexity of the capacitated tree problem[END_REF], where a cost of selection is associated with each arc of the graph, which states that determining whether there exists a rooted tree respecting the capacity constraints and under a given cost of selection is N P-Complete. We then study the design of Steiner arborescences with various notions of robustness: we aim at designing Steiner arborescences while considering the number of terminals disconnected from the root after an arc-deletion in several scenarios. To the best of our knowledge, this problem has not been studied in the literature. We give several formulations for different scenarios and test them on real wind farm data in order to evaluate their impact on the network designed.

In Chapter 2, we introduce a problem called CRkECSN: we aim at designing a minimumcost network where we are able to route a unit of flow from the root to each terminal respecting the capacities (a limited amount of flow can be routed through each arc) even in the event of the deletion of any subset of k arcs in the network built (k being a given integer). We propose several formulations, including a new bilevel one, where the second level is a minmax problem. We also propose an algorithm based on constraints generation and give a method to generate better constraints at each iteration of the algorithm (the enhanced constraint forbids more non-feasible integer solutions than the initial one). We show that the bilevel formulation is a reformulation of another one based on the cut-sets in the graph. We consider the possibility of protecting arcs; those arcs cannot be deleted from the solutions. We give some test results on generated instances and compare the performance of our algorithms.

In Chapter 3, we also study CRkECSN, but in the case of planar graphs. This is motivated by the fact that the wind-farms in offshore environment can often be modeled by grid graphs. The problem of determining whether a graph is k-survivable (i.e. resilient to the deletion of any subset of k arcs) is NP-complete in the general case. However, we derive a theorem which gives properties of the planar dual graph of a k-survivable graph CONCLUSION and extend it to solve this problem in polynomial time in planar graphs, by determining a series of shortest paths. Exact methods for CRkECSN can only solve relatively small size instances. For this reason, we also describe a tabu search algorithm that can handle much larger instances, provided they are planar, and we have shown that it typically produces optimal solutions when these are known. Our algorithm has very low computing times, which makes it particularly interesting in practice, for example for the design of survivable wind farm collection networks with hundreds of wind turbines.

In Chapter 4, we study the problem of designing a cabling network for offshore wind farms while respecting the load flow equations. The load flow analysis corresponds to a non-linear system which allows to determine the state of the network (computations of phase voltages, powers and currents at each node or cable of the network), and then ensure that the power routed through each cable is smaller than its maximum capacity. We use a DC current approximation in order to obtain linear equations. Those equations are added to a Mixed-Integer Program (MIP) and we show that, whenever these constraints are satisfied, the load flow equations are satisfied and the final network is connected. We first give a MIP which allows to solve the problem in the non-robust case (where we do not consider the possibility of breakdowns on the arcs). In a second time, we give a MIP for the case where k = 1 breakdown can occur and a constraints generation algorithm to solve it. We test those MIP on real data given for an offshore wind farm. Finally, we give a bilevel formulation designed to solve the problem for general values of k, and give ideas on how to solve it efficiently.

Research directions

The work presented in this thesis has lead to several questions or interesting research paths that would be appealing to investigate in the future.

It appears that the electricity constraints we studied are easier to take into account when we consider arborescence networks. One of the problems that could be worth study-

Thomas RIDREMONT Design of robust networks. Application to the design of wind farm cabling networks.

Résumé :

Aujourd'hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l'énergie. En particulier, il est devenu nécessaire d'optimiser la façon dont sont conçus les réseaux permettant de produire de l'énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d'électricité via des centrales thermiques ou nucléaires.

Nous nous intéressons dans cette thèse à la conception du câblage collectant l'énergie dans les parcs éoliens. On connaît alors la position de l'ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l'énergie doit être acheminée. On connaît également la position des câbles que l'on peut construire, leurs capacités, et la position des noeuds d'interconnexion possibles. Il s'agit de déterminer un câblage de coût minimal permettant de relier l'ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau.

Mots clés :

Recherche opérationnelle, Optimisation combinatoire, Conception de réseaux robustes, Théorie des graphes, Programmation en nombres entiers, Câblage de parcs éoliens.

Abstract :

Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.

We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimization problem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.