Robust capacitated trees and networks with uniform
demands ∗
Cédric Bentz

(1)

, Marie-Christine Costa
(1)

(2)

, Pierre-Louis Poirion

(3)

, Thomas Ridremont

CEDRIC, CNAM, 292 rue Saint-Martin 75003, Paris, France

ENSTA ParisTech (and CEDRIC-CNAM) 828, Boulevard des Maréchaux 91762 Palaiseau Cedex
(3)
(4)

arXiv:1801.04696v1 [math.OC] 15 Jan 2018

(2)

Huawei (and CEDRIC-CNAM), France

CEDRIC, CNAM (and ENSTA ParisTech), 292 rue Saint-Martin 75003, Paris, France

January 16, 2018

Abstract
We are interested in the design of robust (or resilient) capacitated rooted Steiner networks
in case of terminals with uniform demands. Formally, we are given a graph, capacity and
cost functions on the edges, a root, a subset of nodes called terminals, and a bound k on
the number of edge failures. We first study the problem where k = 1 and the network that
we want to design must be a tree covering the root and the terminals: we give complexity
results and propose models to optimize both the cost of the tree and the number of terminals
disconnected from the root in the worst case of an edge failure, while respecting the capacity
constraints on the edges. Second, we consider the problem of computing a minimum-cost
survivable network, i.e., a network that covers the root and terminals even after the removal
of any k edges, while still respecting the capacity constraints on the edges. We also consider
the possibility of protecting a given number of edges. We propose three different formulations:
a cut-set based formulation, a flow based one, and a bilevel one (with an attacker and a
defender). We propose algorithms to solve each formulation and compare their efficiency.

1

Introduction

Nowadays, the design of networks is crucial in many fields such as transport, telecommunications
or energy. Here, we are interested in the design of robust (or resilient) networks, for certain notions of robustness which will be described later. Formally, we are given a graph G, capacity and
cost functions on the edges, a root, and a subset of nodes called terminals, and we want to select
nodes and edges of G to build a minimum-cost network linking the root to the terminals, while
respecting the capacity constraints on the edges. We assume that some edges can break down,
and that there is a bound k on the number of edge failures. This paper deals with the special
case where the demand is identical for each terminal, i.e., the flow from the root to each terminal
is a constant, and hence can be set to 1 without loss of generality. The uncertainty considered
here concerns the breakdowns, and we aim to protect the network to be built against the worst case.
We first study the case where the network we want to build is an arborescence (rooted tree). The
problem corresponds to the capacitated Steiner tree (or arborescence) problem which has been
studied for instance in [2, 8, 11, 14]. We assume that one arc can break down, and we aim at
generating a robust arborescence, i.e., an arborescence that minimizes the number of terminals
disconnected from the root in the worst case of a breakdown. This can model, in particular, the
problem of wiring networks in windfarms, in order to route the energy produced by the wind
turbines to the sub-station, while respecting some technical constraints (such as cable capacities,
non-splitting constraints, etc.; see [13, 18]).
∗ This work was partially supported by the PGMO Programme Gaspard Monge pour l’optimisation et la recherche
opérationnelle de la Fondation Mathématique Jacques Hadamard.

1

(4)

Then, we study the so-called Capacitated Rooted k-Edge Connected Steiner Network problem : we
aim to design a minimum-cost network in which, after the failure of any k arcs, we can still route
one unit of flow from the root to each terminal. This problem is similar to the Survivable Network
Design problem (see for instance [12]). However, on the one hand, the authors of [12] do not take
into account the arc-capacities. On the other hand, in the latter problem there is a requirement
rst for each pair of vertices (s, t); this means that there must be a path from vertex s to t after
any (rst − 1) arc deletions (in our problem, the edge-survivability requirements are either (k + 1)
or 0). A survey and other work on this problem are available in [10, 16]. In [5], a method based
on Benders decomposition is proposed for a problem with hop-constraints. In [3, 15, 19], the authors take capacities into account, but they allocate it whereas, in our problem, the capacities are
fixed. Studies on multicommodity versions of the problem are also available in [7, 21]. Polyhedral
studies have also been conducted on problems corresponding to the uncapacitated [1] or unrooted
[4] version of our problem. Eventually, we introduce the Capacitated Protected Rooted k-Edge
Connected Steiner Network Problem, where a subset of arcs may be protected and thus cannot
break down.
We denote the given underlying graph by G = (V, E, c, u), where c and u are respectively the cost
and the capacity functions on the set of edges E. We are also given a set T ⊆ V of terminals
and a root r ∈ V \ T . The given graph can be directed or undirected (this will be specified in the
following), but the Steiner tree or network to be built is always directed from the root towards
the terminals. Since we consider a uniform demand at the terminals, the capacity uij , defined as
the maximum amount of flow that can be routed from the root to the terminals through the arc
(i, j), can also be defined as the maximum number of terminals that can be connected to the root
through (i, j). Hence, we can assume without loss of generality that u(e) is a positive integer for
−
each e ∈ E. Given a digraph G = (V, A), we will refer to Γ+
G (v) and ΓG (v) as the set of successors
and predecessors of a vertex v ∈ V in G, respectively. In the case where G is an undirected graph,
we will refer to ΓG (v) as the neighbors of v in G.
In Section 2, we study the problem of finding a Steiner or spanning arborescence taking into
account both the cost and the number of terminals disconnected from the root in the worst case
of an edge breakdown. We provide a complexity result, that proves that deciding whether there
exists a spanning arborescence respecting the capacity constraints is an NP-Complete problem;
that corresponds to the special case where there is a demand equal to 1 at each node (except
the root). We also propose different formulations, considering the criteria either as objectives
or as constraints with given bounds (on the costs and/or the maximum number of disconnected
terminals). Then, we compare these formulations by testing them on real windfarm data.
In Section 3, we study the capacitated rooted k-edge connected Steiner network problem, which
amounts to searching for a robust network, i.e., a network that, in the worst case of k arcs failure,
can still route one unit of flow from the root to each terminal while respecting the capacity constraints. We give two formulations based on cut-sets and flows respectively, as well as a third one,
which is actually a bilevel program whose second level is a min-max problem, with an attacker and
a defender. Then, we consider the case where a set of arcs can be protected (and thus cannot break
down), and show how to adapt these three formulations in this case. We also propose methods
based both on integer linear programming and constraints generation, as well as valid inequalities,
to solve each of the formulations we obtained.
Finally, in Section 4, we compare the efficiency of the methods proposed in the previous section,
by testing them on a large set of randomly generated data, before concluding.

2

Robust arborescences

In this section, 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 windfarm cabling problems (see Section 1), 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

2

then corresponds to a Steiner anti-arborescence. The wind turbines are identical, and the wind
is assumed to blow uniformly, so we can assume 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 windturbine
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 antiarborescence. 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 propose mathematical formulations which are tested on real windfarm instances.

2.1

Definition of problems and complexity results.

We assume in this section that the graph G = (V, E) is undirected and, when considering a subgraph G0 = (V 0 , A0 ) of G to which we give an orientation, we write V 0 ⊆ V and A0 ⊆ E (arcs of
G0 correspond to edges of G). We define the robust problem without capacity constraint 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 = (VS , AS ) such that VS ⊆ V , AS ⊆ E and T ⊂ VS , which is
rooted at r and minimizes the number of terminals disconnected from r when an arc a is removed
from AS , 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 2.1 a) There is an optimal solution S ∗ = (V, A∗ ) 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 ∈ VS∗ ∩ ΓG (r).
Proof: Let S = (V, AS ) be an optimal solution of RSpA such that there is v ∈ ΓG (r) with
(r, v) ∈
/ AS , and let w be the predecessor of v in the path from r to v in S. If we remove (w, v)
from AS 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) ∈
/ AS yields a solution S ∗ verifying the property.
The proof is similar for RStA, by replacing ΓG (r) by VS∗ ∩ ΓG (r): if we remove (w, v) from AS 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.
QUESTION: Is there a spanning arborescence S = (VS , AS ) of G, rooted at r, such that the size
of any subarborescence of S not containing r is at most β?
Theorem 2.1 RSpAF is NP-Complete.
3

Proof: We introduce the 3-Partition problem [9] 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 di , i = 1, .., 3m, and a positive integer B such
P
that i=1,...,3m di = mB and B/4 < di < B/2 ∀i = 1, ..., 3m.
QUESTION: Can D be partitioned into m disjoints subsets M1 , M2 , ..., Mm of three 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 vj with an edge [r, vj ] for
j = 1, ..., m, each vertex vj corresponding to a set Mj . We add 3m vertices wi and the edges [vj , wi ]
for all j = 1, .., m and all i = 1, .., 3m, each vertex wi corresponding to the element di of D (the
subgraph induced by the vertices vj and wi is complete bipartite). Finally, for each i = 1, .., 3m,
we add di − 1 vertices adjacent to wi : the subgraph induced by those vertices and the vertices wi
is made of 3m stars. See Figure 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 vj is smaller than or equal to B + 1. If there is a solution to
RSpAF on G, then, from the proof of Property 2.1, there is a solution S such that (r, vj ) ∈ S
∀j = 1, ..., m, and each wi is connected to exactly one vj , otherwise there is a cycle. Given a vertex
v ∈ S,
P let S(v) be the subarborescence of S rooted at v: ∀j = 1, ..., m, we have |S(vj )| ≤ B + 1
and j=1,..,m |S(vj )| = |V \ {r}| = mB + m. Thus, ∀j = 1, ..., m, |S(vj )| = B + 1 and S(vj )
contains vj and several vertices wi , each having di − 1 successors in S. Finally, the constraints
B/4 < di < B/2 imply that, ∀j = 1, ..., m, vj is connected to exactly 3 vertices wi denoted in the
following by wj1 , wj2 and wj3 , and such that |S(wj1 )| + |S(wj2 )| + |S(wj3 )| = |S(vj )| − 1 = B.
Then, it is easy to obtain a solution to the 3-Partition instance. For each j = 1, .., m, we set
Mj = {|S(wj1 )|, |S(wj2 )|, |S(wj3 )|} = {dj1 , dj2 , dj3 }. We have m disjoint sets, each of size B, which
cover exactly D. For the instance given in Figure 1, a solution to 3-Partition can be associated
with the arborescence given in thick: M1 = {5, 3, 3} and M2 = {4, 4, 3}.
Similarly, from a solution to the 3-Partition instance, it is easy to obtain a solution S to RSpAF
for the associated graph G.
The 3-Partition problem is NP-Complete in the strong sense, meaning that it remains NP-Complete
even if the integers in D are bounded above by a polynomial in m. Thus, the reduction can be
done in polynomial time and RSpAF, which is clearly in NP, is NP-Complete.

RSpAF being NP-Complete, RSpA is NP-Hard, and so is RCStA because it is a generalization
of RSpA. Let us now consider capacity constraints on the edges. RSpAF can be seen as a special
case of the general capacitated spanning arborescence problem where the demand at each node is
an integer (our demands are all equal to 1), and hence from Theorem 2.1 we obtain the following
corollary:
Corollary 2.2 Given a graph G = (V, E, 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).
This extends the following result due to Papadimitriou [17]: 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.

4

r

v1

w1

w2

v2

w3

w4

w5

w6

Figure 1: Graph and RSpAF solution resulting from the 3-Partition instance in which m = 2,
B = 11, D = {5, 3, 4, 3, 4, 3}
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)
INSTANCE: A connected graph G = (V, E, r, T, u) with r ∈ V , T ⊆ V \ {r} and u a positive
integer function on E.
PROBLEM: Find an arborescence S = (VS , AS ) with VS ⊆ V and AS ⊆ 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 AS , in the worst case.

2.2

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.
Let G = (V, A, r, T, u, c) be a directed graph with 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 yij and the integer variable
xij , where yij equals 1 if and only if the arc (i, j) is selected in the final solution, and xij 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 :

5

T =















P
x∈N

|A|

|A|

, y ∈ {0, 1}

xij −

(i,j)∈A

P

P

xjk

(j,k)∈A

yij

≤


 |T |
−1
=

0

if j = r
if j ∈ T
else

∀j ∈ V \ {r} 





∀(i, j) ∈ A

1

(i,j)∈A

xij

≤

∀j ∈ V









uij yij

In the following, we write (x, y) ∈ T when we consider a couple of variables verifying the contraints
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 [6]:
CStA

min
(x,y)∈T

X

cij yij

(i,j)∈A

As explained previously, we evaluate the robustness by considering the number of terminals disconnected from the root in a worst scenario, that is, the maximum number of terminals connected
through an arc incident to the root, which is equal to maxj∈Γ+ (r) xrj . Let R be a fixed bound
G
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
(CStAbounded−robust ):
P
min
cij yij
(x,y)∈T
(i,j)∈A
CStAbounded−robust
s.t.
max xrj ≤ R
j∈Γ+
G (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)

xrj

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:
min
RCStAbounded−cost

(x,y)∈T

s.t.

max
P

j∈Γ+
G (r)

xrj

cij yij ≤ C

(i,j)∈A

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 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
P on an arc (i, j), j ∈ ΓG (i). We
define the "balanced robustness" as the sum of these values:
xij .
i∈V maxj∈Γ+
G (i)
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
6

with bounded balanced robustness, where we bound the balanced robustness of a solution by a
given value BR:
P
min
cij yij
(x,y)∈T
(i,j)∈A
P
CStAbounded−balanced_robust
s.t.
max
xij ≤ BR
+
i∈V j∈ΓG (i)

The following formulation aims at computing the best balanced robustness:
BRCStA

X

min
(x,y)∈T

i∈V

max

j∈Γ+
G (i)

xij

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:
P
max
min
xij
+
(x,y)∈T

s.t.

BRCStAbounded−robust−cost

i∈V j∈ΓG (i)

max
P

j∈Γ+
G (r)

xrj ≤ R

cij yij ≤ C

(i,j)∈A

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 1a and 1b. Figure
2 allows to visually compare the arborescences obtained according to the different models for the
fourth data set (the filled circles correspond to terminals).
Figure 2a 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 Figure 2b for the associated solution on
∗
the test instance. Then, to obtain the minimum cost of a most robust solution, denoted by CR
∗,
we solve CStAbounded−robust with R = R∗ : notice that the constraint is saturated in any feasible
∗
∗
∗
represents the "cost of robustness", i.e., the percentage
solution. Then, ∆Crob = (CR
∗ − C )/C
of augmentation of the cost to get a robust solution.
In the same way, let BR∗ be the best balanced robustness (optimal value of BRCStA, not given in
the table); see Figure 2c for the associated solution on the test instance. The cost of a solution with
∗
the best balanced robustness, denoted by CBR
∗ , is obtained by solving CStAbounded−balanced_robust
∗
∗
∗
with BR = BR∗ , and ∆Cbrob = (CBR
−
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 behaviour of the robustness when we bound the cost to a value close to the
one of an optimal non robust arborescence : R8 (resp. R12 ) corresponds to the optimal value of
RCStAbounded−cost with a bound C = 1.08C ∗ (resp. C = 1.12C ∗ ).
We now analyse 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 2c).
As we can see on Table 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%.

7

Finally, we compare the optimal robustness R∗ to the robustness of the balanced arborescence
Sb obtained by solving BRCStA, i.e., we compute in Sb (see Figure 2c) the maximum number
of terminals which are disconnected after the deletion of an arc incident to the root. Let RBR∗
be this number, shown in the last column of Table 1b. For the test instances, the values of R∗
and RBR∗ are the same, which means that Sb 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.
Set
1
2
3
4

|V|
91
143
220
255

|E|
220
382
510
662

|T|
42
40
88
73

Set
1
2
3
4

R∗
21
20
22
37

(a) Data parameters

R8
35
21
32
41

R12
29
20
30
38

∆Crob
0.18
0.09
0.24
0.19

∆Cbrob
0.56
0.64
0.33
0.37

RBR∗
21
20
22
37

(b) Results on robust arborescences

Table 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 2b), 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 2c), 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 BRCStAbounded−robust−cost in Figure 2d), 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).

3
3.1

Capacitated Rooted k-Edge Connected Steiner Network
problem (CRkECSN)
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 shall consider is then a network rooted at a
given root and covering a given set of terminals, and such that, after deleting any k arcs, it is still
possible to route a unit of flow from the root to each terminal, 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 r ∈ V , T ⊆ V \ {r}, a capacity
function u on A, a cost function c on A, an integer k with 1 ≤ k ≤ |A| − 1.
QUESTION: Find a subset A0 ⊆ 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 A0 , even if any k arcs in A0 are deleted.
As we consider uniform production at the terminals, we also assume that u is an integer function.
Property 3.1 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
8

(b) RCStA
(a) CStA

(c) BRCStA

(d) BRCStAbounded−robust−cost

Figure 2: Resulting arborescences

9

at least a 2-edge-connected graph in the underlying undirected graph.
Proof: The first part of the property is trivial. Let G0 be an inclusion-wise minimal feasible
solution and let assume G0 is not 2-edge-connected in the underlying undirected graph. Then
there exists at least one edge whose removal cuts G0 into two parts. If the part that does not
include the root contains terminals, then G0 is clearly not a feasible solution because, if we remove
this edge, then at least one terminal cannot be reached from the root. Otherwise, G0 is not
inclusion-wise minimal because, if we remove this edge, then the resulting graph is still a feasible
solution. Hence, any inclusion-wise minimal feasible solution induces at least a 2-edge-connected
graph.

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 cts = 0 and uts = 1. Then, s is added to V and the fictive arcs are added to A, and
we denote by AI the set of initial arcs. 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 graph. For each subset S ⊂ V , let δ − (S) be the set of arcs entering S. We have
δ − (S) = {(i, j) ∈ A | i ∈ V \ S, j ∈ S}.

3.2
3.2.1

Formulations
Cutset formulation

We introduce, for each (i, j) ∈ A, a binary variable yij equal to 1 if the arc (i, j) is selected in A0 ,
0 otherwise. Consider the r − s cuts [V \ VS , VS ] with VS ⊂ V , r ∈ V \ VS , s ∈ VS and VS 6= {s},
and let S be the set of all the associated cut-sets S in A, i.e. S = δ − (VS ) for each VS . S is the set
of r − s cutsets except the one implying only fictive arcs. Notice that if S ∈ S then S ∩ A0 is a
cut-set in the selected network. For any set S ∈ S, let CkS be the set of subsets of S of size k. For
each S, we define MS as the maximum capacity of a subset of k selected arcs of S:
MS

=

max

C∈CkS

X

uij yij

(3.1a)

(i,j)∈C

MS 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:
min

X

y

cij yij

(i,j)∈A

s.t.

X

uij yij − MS ≥ |T |

∀S ∈ S

(3.2a)

(i,j)∈S

yij ∈ {0, 1}

∀(i, j) ∈ A

The constraints (3.2a) 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 capacities. 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 yij = 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. If a constraint is not satisfied, it means that, by removing k arcs, the
capacity of the min-cut in the graph induced by y becomes smaller than |T |. Those constraints
are also sufficient to ensure a feasible network. Indeed, if they are satisfied for each cut-set S ∈ S,
it means that you cannot find a set of k arcs whose removal will induce a min-cut with capacity
smaller than |T | (which is a necessary and sufficient condition for the existence of a flow of value
|T |).

10

The constraints (3.2a) are non linear because of the use of the maximum operator in the definition
of MS . To linearize it, we can rewrite (3.2a) as follows:
X

uij yij

≥

∀S ∈ S, ∀C ∈ CkS

|T |

(3.3a)

(i,j)∈S\C

The number of constraints (3.3a) being exponential, we propose a constraints generation algorithm.
We begin with a small number of constraints (3.3a), associated with a small subset of S. We obtain
a lower bound for our problem. Then we select a cut-set that does not verify some constraint (3.2a):
given a network induced by the arcs (i, j) such that ŷij = 1 (where ŷ is the current value of y),
we aim to find the cut of minimum residual capacity once we delete its k most capacitated arcs.
If this capacity is smaller than |T |, we add the constraints associated with this cut-set, 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 AI 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 uij ŷij , except for the k arcs of C whose capacities are set to 0. Otherwise, the
following MIP can be used:
P

min

s,d,v

uij ŷij sij

(i,j)∈A

s.t sij + dij − vi + vj

≥ 0

∀(i, j) ∈ A

(3.4a)

vr

=

1

(3.4b)

vs
X

=

0

(3.4c)

≤ k

(3.4d)

=

(3.4e)

dij

(i,j)∈A

X

dts

0

t∈T

s, d ∈ {0, 1}|A| ,

v ∈ {0, 1}|V |

(3.4f)

In this MIP, the variable v defines a r − s-cut on the network: any vertex j with vj = 1 is in the
same part of the cut as r, and any vertex i with vi = 0 is in the same part as s. The variable d
defines the deleted arcs, dij = 1 if and only if arc (i, j) is deleted, whereas s defines the selected
arcs, sij = 1 if and only if arc (i, j) is selected in the cut. Then, the constraints (3.4a) ensure that
Ŝ = {(i, j) s.t. sij = 1 or dij = 1} defines a cutset in the current network, and the objective funcP
tion (i,j)∈A uij ŷij sij represents the residual capacity of Ŝ, i.e., the capacity of the undeleted arcs
of Ŝ. the constraints (3.4b) and (3.4c) ensure that the root and the sink are not in the same part
of the cut. The constraints (3.4d) and (3.4e) ensure that there are no more than k arc deletions,
and that no fictive arc can be deleted. Notice that, in any optimal solution, the constraint (3.4d)
is saturated and, for each arc (i, j), at most one of sij and dij is equal to 1. If the solution provides
a cutset with a residual capacity at least equal to |T |, then the solution is feasible, and so optimal.
Otherwise, we add the associated constraint to the main MIP.
In the case of a uniform capacity U on each arc a ∈ AI , MS in the constraints (3.2a) becomes a
constant equal to kU and hence these constraints are linear, and the constraints (3.3a) 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

X

y

cij yij

(i,j)∈A

s.t.

X

uij yij ≥ |T | + kU

∀S ∈ S

(3.5a)

1

∀t ∈ T

(3.5b)

yij ∈ {0, 1}

∀(i, j) ∈ A

(i,j)∈S

yts

=

11

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

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 in AI . We introduce
the variable xF
ij which represents the amount of flow routed through the arc (i, j) ∈ A when the
scenario F ∈ F occurs. The variable y is defined as in the previous formulation (see Subsection
3.2.1). We propose the following flow formulation:
min

X

x,y

cij yij

(i,j)∈A
X
s.t.
xF
ij
i∈Γ− (j)
X
xF
ts
−
t∈Γ (s)

xF
ij
xF
ij
x∈

−

X

xF
jk = 0

∀j ∈ V \ {r, s}, ∀F ∈ F

(3.6a)

∀F ∈ F

(3.6b)

k∈Γ+ (j)

=

|T |

≤

uij yij

∀(i, j) ∈ A, ∀F ∈ F

(3.6c)

=

0

∀F ∈ F, ∀(i, j) ∈ F

(3.6d)

|A|×|F |
R+
,

y ∈ {0, 1}|A|

The constraints (3.6a) and (3.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. The
constraints (3.6c) ensure that the arc capacities are respected for each arc-failure scenario F ∈ F.
The constraints (3.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 |E| different networks
with integer capacities. Then, for any value of y ∈ {0, 1}|E| , there exists a solution where x is
integer. As only the variable y is involved in the objective function, we have that there always
exists an optimal solution with x integer.
The number of variables xF
ij and constraints (3.6a) and (3.6b) 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 in
a flow network [20]: we search for the k arcs which, once simultaneously deleted, reduce the most
the value of a maximum s − t flow. We use a procedure similar to the one used in Subsection 3.2.1:
for small values of k, we compute a maximum s − t flow for each combination of k selected arcs of
AI . 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 optimal. If k is too big, we use an auxiliary MIP.
In order to adapt the formulation to the undirected case with a set of edges E instead of a set of
F
+
−
arcs A, one can define for each [i, j] ∈ E the variables yij , xF
ij and xji . The function Γ and Γ
are replaced by the function Γ in the constraints (3.6a) and (3.6b), while the constraints (3.6c)
and (3.6d) are replaced by:
F
xF
ij + xji

xF
ij

+

≤
xF
ji

uij yij

∀[i, j] ∈ E, ∀F ∈ F

(3.7a)

=

∀F ∈ F, ∀[i, j] ∈ F

(3.7b)

0

A feasible solution induced by y and x implies a flow of value |T | for each scenario F ∈ F. Then,
F
if a given solution yields a strictly positive flow on both xF
ij and xji for a given edge [i, j] and a
given scenario F , it is trivial that there exists another flow at least as good as this one, but in
F
which the amount of flow on either xF
ij or xji is 0.

12

3.2.3

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 xij 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 3.2.1.
We also introduce the binary variables bij , ∀(i, j) ∈ A: bij = 1 if and only if the attacker chooses
to delete the arc (i, j). Moreover, we assume without loss of generality that there is no arc of the
form (v, r) for some vertex v. Then, we can define the following polyhedron:
P
P


xij −
xjk = 0 ∀j ∈ V \ {r, s} 





i∈Γ− (j)
k∈Γ+ (j)


|A|
x
≤
u
y
∀(i,
j)
∈
A
ij
ij ij
X (y, b) = x ∈ R
.




xij ≤ uij (1 − bij )
∀(i, j) ∈ A




xij ≥ 0
∀(i, j) ∈ A
This polyhedron X (y, b) corresponds to the set of possible flows on the subgraph of G induced by
the arcs (i, j) such that yij = 1, provided they have not been deleted (i.e. bij = 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 polyhedrons:
P
B = { b ∈ {0, 1}|A| |
(i,j)∈A bij ≤ k ; bts = 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:
min

y∈{0,1}|A|

X

cij yij

(i,j)∈A

s.t. f (y) ≥ |T |
where f (y) =

(3.8a)
min
b∈B

max
x∈X (y,b)

X

xrj

(3.8b)

j∈Γ+ (r)

where {(i, j) s.t. yij = 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 (3.8a)).
Consider the max problem in the lower level: at this stage, y and b are already fixed; we refer to
their values as ŷ 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. Then, adding the second set of capacity constraints is equivalent
to appending the identity matrix to M : the matrix remains totally unimodular and, as 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 this max problem of the lower level, there always exists a feasible flow of value 0 and the problem
is also trivially upper bounded. Hence, the strong duality holds and we can introduce the dual of

13

the lower level problem, after a slight reformulation due to the totally unimodular matrix:
P

min

λ,µ,γ

P

uij ŷij λij +

(i,j)∈A

uij (1 − b̂ij )γij

(i,j)∈A

s.t λij + γij − µi + µj

≥ 0

µr
µs
|A|

λ, γ ∈ [0, 1]

,

µ ∈ [0, 1]

∀(i, j) ∈ A

(3.9a)

=

1

(3.9b)

=

0

(3.9c)

|V |

(3.9d)

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). The variables γ 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, otherwise
we have γij = λij = 0. 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 b̂ij = ŷ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 b̂ij = ŷ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 the dual constraints (3.9a)−(3.9d).
As the lower level can be reformulated as a min − min function by using the dual described above,
it can then be rewritten as follows:
P
min
uij ŷij λij + uij (1 − bij )γij
b,λ,µ,γ

(2LP ) s.t

(i,j)∈A

b∈B
(λ, µ, γ) ∈ D

At this point, b is a variable, so the objective function is non-linear. We linearize the terms bij γij
in a classical way by introducing binary variables lij verifying the set of constraints defined by
L(b, γ):


lij ≤ bij
∀(i, j) ∈ A 





lij ≤ γij
∀(i, j) ∈ A
|A|
L(b, γ) = l ∈ R
lij ≥ γij − (1 − bij ) ∀(i, j) ∈ A 





lij ≥ 0
∀(i, j) ∈ A
P
We also define the function g(y, λ, γ, l) = (i,j)∈A [uij yij λij + uij γij − uij lij ]. We can then rewrite
the bilevel program as:
P
cij yij
min
y∈{0,1}|A|

s.t

(i,j)∈A

f (y) ≥ |T |
where
f (y)

=

min

b,λ,γ,µ,l

s.t.

g(y, λ, γ, l)
b∈B
(λ, µ, γ) ∈ D
l ∈ L(b, γ)

We can then consider the convex hull of the lower-level polyhedron, 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

14

formulation as a single-level one as follows:
min

X

cij yij

(i,j)∈A

s.t. g(y, λ̂h , γ̂ h , ˆlh ) ≥ |T |

∀h ∈ H

(3.10b)

b∈B

(3.10c)

(λ, µ, γ) ∈ D

(3.10d)

l ∈ L(b, γ)

(3.10e)

y ∈ {0, 1}
(BP)

(3.10a)

|A|

The constraints (3.10a) ensure that, for each extreme point of H, f (y) is greater than |T | (i.e., the
minimum value of f (y) over the polyhedron defined by the constraints (3.10c)−(3.10d) is greater
than |T |), meaning that the value of a maximum flow cannot become smaller than |T |, even after
any k breakdowns.
Remark 3.1 In (BP), g(y, λ, γ, l) is non-linear because of the products yij λij , but they can be
linearized as it has been done for bij γij above.
However, there is an exponential number of constraints (3.10a), and we do not know how to
describe explicitly the convex hull of H. To tackle this issue, we use a constraints generation
algorithm where we relax the constraints (3.10a) and use (2LP ) as the separation problem: while
the optimum value of (2LP ) is smaller than |T | for the current optimal solution ŷ, we generate the
constraints (3.10a) associated with the extreme point whose coordinates are the optimal values of
(b, λ, γ, µ, l) in (2LP ).
1
2
Property 3.2 Let ŷ 1 and ŷ 2 be two feasible solutions of (BP) such that ŷ 1 ≥ ŷ 2 , i.e., ŷij
≥ ŷij
for
a
a ˆa
each arc (i, j). If adding a constraint g(y, λ, γ, l) ≤ g(y, λ̂ , γ̂ , l ) makes any solution with y = ŷ 1
infeasible, then it also makes any solution with y = ŷ 2 infeasible.

Proof: For any value (λ̂a , γ̂ a , ˆla ) of (λ, γ, l), we have g(ŷ 1 , λ̂a , γ̂ a , ˆla ) ≥ g(ŷ 2 , λ̂a , γ̂ a , ˆla ) since
ŷ 1 ≥ ŷ 2 (as u and λ are positive). Hence, if g(ŷ 1 , λ̂a , γ̂ a , ˆla ) ≤ |T |−1, then g(ŷ 2 , λa , γ a , la ) ≤ |T |−1.

To improve the cut obtained by solving (2LP ) at each step, we try to inject better values ŷ of
variables y in it. To get these values, we first solve the following problem, and then we compute
the new ŷ accordingly (as explained later). Given a starting solution ŷ, we want 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 the arcs (i, j) such that ŷij = 1 (meaning that,
if we remove k given arcs of the cut-set, its remaining capacity is smaller than |T |). This can be
modeled as follows:
P
min
(i,j)∈A λij
X
s.t
uij ŷij λij
≤ |T | − 1
(3.11a)
(i,j)∈A

X

≤ k

γij

(3.11b)

(i,j)∈A

γts

=

0

∀t ∈ T

(3.11c)

|V |

(λ, µ, γ) ∈ D, µ ∈ {0, 1}

The variables (λ, µ, γ) define a cut as in (2LP ) since they belong to D (recall that D is the set of
constraints (3.9a)−(3.9d)). However, adding the other constraints makes the constraints matrix
not unimodular anymore: thus, we have to set µ as a 0-1 variable. The constraint (3.11a) ensures
that the cut-set selected is non-valid (as defined before). The constraint (3.11b) bounds the number of deleted arcs to at most k, while the constraints (3.11c) forbid the deletion of fictive arcs.
Then, the new values of the ŷij ’s are computed as follows: we set ŷij to 1 for all (i, j) with
λij = γij = 0 and let the others to their current value. It implies that, for each arc (i, j), the new
15

value of ŷij cannot be smaller than the old one, and, using Proposition 3.2, we generate a better
constraint than the original one by computing the extreme points associated with this new value
of ŷ.
In order to obtain a formulation that works for the undirected case, we define for each edge [i, j]
the variables yij , bij , xij and xji . The only modification appears in the polyhedron X (y, b), which
can be modified as follows:
P
P


xij −
xjk = 0 ∀j ∈ V \ {r, s} 



(
(


i∈Γ j)
k∈Γ j)








xij ≤ uij yij
∀[i, j] ∈ E


|E|
xji ≤ uij yij
∀[i, j] ∈ E
X (y, b) = x ∈ R




xij ≤ uij (1 − bij )
∀[i, j] ∈ E








xji ≤ uij (1 − bij )
∀[i, j] ∈ E




xij , xji ≥ 0
∀[i, j] ∈ E
Again, as 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 xij = 0 or xji = 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.

3.3

Addition of protected arcs

Let us now define another version of the problem, where we add the possibility of protecting k 0
arcs. In this version, in addition to A0 , we also select a subset A0p ⊂ A0 with |A0p | ≤ k 0 ; 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).
For each arc (i, j), we define the variable pij as a binary variable equal to 1 if the arc (i, j) is
protected, and to 0 otherwise. We also define the set of values that can be taken by p:
P
P = { p ∈ {0, 1}|A| |
pij ≤ k 0 ; pij ≤ yij ∀(i, j) ∈ A }
(i,j)∈A

This set ensures that there are at most k 0 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.
3.3.1

Cut-set formulation

In the cut-set formulation, the constraints (3.3a) can be replaced by the following ones:
X
(i,j)∈S

uij yij −

X

uij (yij − pij )

≥

|T |

∀S ∈ S, ∀C ∈ CkS

(3.12a)

(i,j)∈C

We check that the capacity of each cut-set minus the capacity of k unprotected arcs of this cutset 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 3.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 3.2.1, we take into account all selected arcs). Considering the MIP, we just have to
add the constraint dij ≤ 1 − p̂ij for each arc (i, j) (where p̂ corresponds to the current value of p).
Remark 3.2 When arcs can be protected, the case of uniform capacities does not admit a simpler
formulation anymore.

16

3.3.2

Flow formulation

In the flow formulation, in addition to the constraint p ∈ P , we can replace the constraints (3.6d)
by the following ones:
xF
ij

≤

uij pij

∀F ∈ F, ∀(i, j) ∈ F

(3.13a)

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-andconstraints generation algorithm as in Subsection 3.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).
3.3.3

Bilevel formulation

In the bilevel formulation, the only polyhedron that needs to be modified is X (y, b), which is
replaced by the following one, denoted by X (y, b, p):
P
P


xij −
xjk = 0 ∀j ∈ V \ {r, s} 



+
−


i∈Γ (j)
k∈Γ (j)


|A|
xij ≤ uij yij
∀(i, j) ∈ A
X (y, b, p) = x ∈ R




xij ≤ uij (1 − bij + pij ) ∀(i, j) ∈ A




xij ≥ 0
∀(i, j) ∈ A
The third constraint ensures that, if an arc is protected, then we can route a flow through this arc
(respecting the capacities) even if the attacker deletes it. The bilevel formulation for the problem
with protected arcs is then:
P
cij yij
min
y∈{0,1}|A| ,p∈P

(i,j)∈A

f (y, p) ≥ |T |
where
f (y, p)

s.t

=

(BPP)

min

b,λ,γ,µ,l

s.t.

gprot (y, p, λ, γ, l)
b∈B
(λ, µ, γ) ∈ D
l ∈ L(b, γ)

P
where gprot (y, p, λ, γ, l) = (i,j)∈A uij yij λij + uij γij − uij lij + uij pij γij . We then use the same
decomposition method to solve the formulation. Property 3.2 can be replaced by the following one
(using the fact that u ≥ 0 and γ ≥ 0):
Property 3.3 Let (ŷ 1 , p̂1 ) and (ŷ 2 , p̂2 ) be two feasible solutions of (BPP) such that ŷ 1 ≥ ŷ 2 and
p̂1 ≥ p̂2 . If adding a constraint gprot (y, p, λ, γ, l) ≤ gprot (y, p, λ̂a , γ̂ a , ˆla ) makes any solution with
(y, p) = (ŷ 1 , p̂1 ) infeasible, then it also makes any solution with (y, p) = (ŷ 2 , p̂2 ) infeasible.
The same MIP can be used to enhance the generated constraint, simply by replacing the constraint
(3.11a) by the following one:
X
uij ŷij λij + p̂ij γij ≤ |T | − 1
(i,j)∈A

3.4

Valid inequalities

In this section, we propose some valid inequalities to enhance the quality of the lower bound
obtained by solving the continuous relaxation.
X

yit

≥

k+1

(i,t)∈A

17

∀t ∈ T

(3.14a)

X

≥

yri

k+1

(3.15a)

(r,i)∈A

Inequalities (3.14a) 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 (3.15a) states the same constraint for the root.
Those two families of inequalities are only true for the case without protection (k 0 = 0). As one
arc can be enough if it is protected, we can replace the previous inequalities by (3.16a) and (3.17a)
in this case.
X

yit

≥

X

yri

1

∀t ∈ T

(3.16a)

1

(3.17a)

(i,t)∈A

≥

(r,i)∈A

Inequalities (3.18a) state that, for each Steiner vertex j, if an arc entering j is selected, then at
most one arc leaving j must be selected. Indeed, in a feasible solution, if there is no arc leaving a
Steiner vertex, then all arcs entering it can be deleted without making the solution infeasible (as
we assumed the arc costs to be positive, this new solution is at least as good as the previous one).
Inequalities (3.19a) state the same for arcs leaving a Steiner vertex j. Those inequalities are valid
in both protected and unprotected versions of the problem.
yij

X

≤

yjk

∀j ∈ V \ {T ∪ {r}}, ∀i ∈ Γ− (j)

(3.18a)

yij

∀j ∈ V \ {T ∪ {r}}, ∀k ∈ Γ+ (j)

(3.19a)

k∈Γ+ (j)

yjk

X

≤

i∈Γ− (j)

Inequalities (3.20a) relate to the Steiner vertices which are adjacent to a terminal, in the unprotected version of the problem. Terminals must have at least k + 1 neighbors in a feasible solution.
Any given terminal t ∈ T has a number of neighbors which are terminals equal to |ΓG (t) ∩ T |.
Then, there must be at least max(0, (k + 1) − |ΓG (t) ∩ T |) neighbors of t which are Steiner vertices
in a feasible solution. As any Steiner vertex selected in an inclusion-wise minimal solution has at
least two incident arcs, we ensure that the number of those arcs (counted with their multiplicity)
is larger than two times the number of necessary Steiner vertices adjacent to t.
X

(

X

yij +

j∈ΓG (t)∩(V \T ) i∈Γ− (j)
G

X

yjk )

≥

2(k + 1 − |ΓG (t) ∩ T |)

∀t ∈ T

(3.20a)

k∈Γ+
G (j)

In the case with protected arcs, each vertex v ∈ T ∪ {r} must have at least k + 1 arcs entering
it (or leaving it, if v = r), except if it has at least one protected arc entering it (or leaving it, if
v = r), which can happen for at most k 0 vertices among these |T | + 1. Hence, we obtain:
X X

yit +

t∈T i∈Γ− (t)
G

4

X

yrj

≥

(|T | + 1 − k 0 )(k + 1) + k 0

(3.21a)

j∈Γ+
G (r)

Results analysis

In this section, we present the results of the three 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. Table 2 shows for each instance
the number associated (I), as well as the number of vertices, terminals, and edges, respectively.
The column opt gives the optimal value of the Capacitated Rooted Steiner Network (CRSN) for
each instance, which corresponds to the case where k = 0. All instances have been generated in
18

the following way: the vertices have been generated in the plane, and the capacity of an arc is
more likely to be high if this arc is close to the root. The arc capacities are high enough to have a
set of feasible solutions to our problems, but low enough to keep the difficulty in those problems.
More precisely, the capacities are chosen randomly among four values: 0.8|T |, 0.6|T | and, except
for the 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.
I
1
2
3
4
5
6
7
8
9
10
11
12

|V|
20
20
20
20
20
25
25
25
25
25
30
30

|T|
2
4
6
12
19
2
5
8
15
24
18
3

|E|
47
46
45
46
46
60
59
61
61
59
74
74

opt
3.43
5.16
7.8
10.73
14.14
4.62
5.78
8.11
10.36
13.93
9.45
3.83

I
13
14
15
16
17
18
19
20
21
22
23

|V|
30
30
30
35
35
35
35
35
40
40
40

|T|
6
9
29
4
7
10
21
34
4
8
12

|E|
73
74
74
89
87
91
89
88
104
103
100

opt
10.52
7.19
13.85
3.17
7.51
8.95
11.58
12.81
6.0
8.83
12.73

I
24
25
26
27
28
29
30
31
32
33
34

|V|
40
40
45
45
45
45
50
50
50
50
50

|T|
24
39
14
27
44
4
5
10
15
30
49

|E|
104
103
118
114
119
119
133
133
131
133
130

opt
10.93
14.95
10.26
17.03
18.74
3.41
6.48
9.75
8.22
12.29
16.05

Table 2: Instance parameters and results of CRSN

Parameters
k
1
2
3
-

I
I1
I2 \ {13, 19}
2,3,6,8
14,18,21,23,25,26
6,8
18,21

%opt
100.0
93.33
100.0
100.0
100.0
100.0

Bilevel
time(s) CRG
18.24
0.3
382.11
0.26
6.9
0.21
209.3
0.22
16.33
0.17
199.25
0.26

it
159
425
72
428
140
418

%opt
100.0
60.0
100.0
50.0
100.0
50.0

Cut-set
time(s) CRG
31.93
0.17
1396.57
0.17
33.9
0.08
1692.22
0.16
35.14
0.13
2472.0
0.17

it
91
389
66
253
89
176

%opt
100.0
100.0
100
-

Flow
time(s) CRG
18.42
0.17
69.28
0.08
246.45
0.13
-

it
12
30
82
-

Table 3: Results on instances with non-uniform capacities and k 0 = 0
Table 3 shows the results obtained, for k ∈ {1, 2, 3} and k 0 = 0, by the three formulations on those
instances with non-uniform capacities. For each value of k, we have computed the results on two
subsets of instances, one called I1 on which we test the three formulations, one called I2 composed
of instances of larger size, on which we test only the bilevel and the cut-set formulations as the
solving time of the flow formulation is too important in that case. The subset I1 is composed of the
instances numbered from 1 to 11 while I2 is composed of the ones numbered from 12 to 28. As some
instances do not admit feasible solutions for some values of k, we remove such instances. Nevertheless, those instances are taken into account in the results when k 0 6= 0 and in the case of uniform
capacities. The column k is the number of arc deletions considered for this subset of instances,
while I gives the numbers of the instances tested. For each formulation, %opt corresponds to the
percentage of instances solved to optimality, time shows the mean solving time (in seconds) for this
subset, CRG corresponds to the mean gap between the optimal value of the continuous (or linear)
relaxation and the optimal value of the problem and it corresponds to the mean value of iterations.
As we can see in this table, on small instances and small values of k, the three formulations can
be competitive. However, as the sizes of the instances and value of k grow, the bilevel formulation
tends to be the most efficient one, while the flow formulation seems to be the less effective one,
despite the fact that the optimal values of the continuous relaxation of the flow and cut-set formulations yield the same value on this set of instances, and are better than the one of the bilevel
formulation in this case. We can also notice that, on those instances, the connectivity requirements
have a high impact on the cost of an optimal solution, as this cost raises consequently as k increases.
Table 4 shows the results in a similar way than in Table 3, but in the case where the number k 0 of
arcs that can be protected is between 1 and 3. In this case, one can notice that the optimal value
of the continuous relaxation of the cut-set formulation do not yields the same value that the flow
formulation one. However, on those instances, the optimal value of the continuous relaxation of the
cut-set formulation yield values at least as good as the two other ones. However, as in the previous
19

Parameters
k
1
1
1
2
2
2
3
3
3
-

k’
1
2
3
1
2
3
1
2
3
-

%opt
100.0
87.5
100.0
81.25
100.0
82.35
100.0
85.71
100.0
80.0
100.0
68.75
100.0
75.0
100.0
100.0
100.0
90.0

I
I1
I2
I1
I2
I1
I2
I1 \ {1, 4, 7, 9, 10}
I2 \ {13, 19, 28}
I1 \ {9, 10}
I2 \ {19, 28}
I1 \ {9}
I2 \ {28}
6,8
16,18,21,26
2,3,6,8
12,14,16,17,18,21,22,23,26
2,3,5,6,8
I2 \ {15, 19, 20, 24, 25, 28}

Bilevel
time(s) CRG
56.62
0.41
659.4
0.44
62.17
0.42
843.08
0.45
96.23
0.41
909.16
0.45
40.48
0.39
715.5
0.4
62.6
0.37
1146.17
0.43
54.54
0.39
1548.31
0.46
12.1
0.44
841.42
0.37
16.97
0.46
462.28
0.44
24.02
0.26
877.32
0.49

it
251
580
274
638
301
694
216
634
253
730
251
915
88
516
170
576
203
764

%opt
90.0
18.75
90.91
18.75
90.0
17.65
83.33
21.43
77.78
13.33
88.89
12.5
100.0
50.0
100.0
12.5
75.0
20.0

Cut-set
time(s) CRG
361.59
0.27
2556.11
0.32
436.87
0.28
2594.5
0.32
677.15
0.28
2551.54
0.32
760.57
0.27
2482.98
0.3
700.6
0.26
2623.81
0.32
416.84
0.28
2705.04
0.35
81.8
0.2
1634.7
0.28
183.33
0.26
2792.88
0.32
834.25
0.25
2553.8
0.37

it
122
411
130
420
123
434
96
296
96
290
97
292
97
116
102
244
103
183

%opt
90.0
63.64
70.0
66.67
66.67
66.67
100.0
66.67
75.0
-

Flow
time(s)
746.62
1199.01
1241.38
1343.0
1102.47
1488.62
304.6
1122.27
1363.18
-

CRG
0.32
0.35
0.35
0.32
0.36
0.4
0.2
0.33
0.4
-

it
22
27
27
102
97
116
29
144
172
-

Table 4: Results on instances with non-uniform capacities and k 0 ∈ {1, 2, 3}
case, the bilevel formulation seems to be the most efficient one as the sizes of the instances grow.
The results obtained with the three formulations also confirm that the solving time of an instance
is sensitive to the value of k 0 : when this parameter grows, the solving time significantly increases.
3,000
2,500

BF
CF
FF

Time (s)

2,000
1,500
1,000
500
0
Number of the instance
Figure 3: Solving time of the different instances regarding the three formulations
In Figure 3, we can see the solving time for the bilevel, the cut-set and the flow formulations
(respectively BF, CF, and FF in the legend). Figures 3 and 4 present the results obtained on
instances numbered from 1 to 29. The solving time is still bounded by 3000 seconds (when the
solving time is equal to 3000 in this figure, it means that the instance has not been solved at the
end of the allocated time). It shows that the bilevel formulation is more resilient to the growth of
the instances size, whereas the flow formulation seems to be the more sensitive one.
Figure 4 shows the evolution of the gap between the optimal values of the different continuous
relaxations and the optimal value of the problem on each instance, for k = 1 and k 0 ∈ {0, 1}. In
the legend, gap0B (respectively gap0C ) corresponds to the gap (in percentage) between the optimal
value of the continuous relaxation of the bilevel (respectively cut-set) formulation and the optimal
value of the problem when k 0 = 0, whereas gap1B (respectively gap1C ) deals with the case where
k 0 = 1. First, we can see that the gap for the cut-set formulation is better than the one for the
bilevel formulation in both cases. Second, one can notice that the addition of protected arcs greatly
20

0.5

0.4

Gap

0.3

0.2

0.1
gap0B

0

1

2

3

4

5

6

7

8

gap0C

gap1B

gap1C

9 11 13 14 15 16 17 18 20 21 22 23 24 25 28 29

Number of the instance
Figure 4: Gap between the optimal values of the bilevel and cut-set continuous relaxations and
the optimal value of the problem for the different instances when k = 1 and k 0 ∈ {0, 1}
I
2
3
8
I
22
23
24
29
-

Parameters
U k
opt
5 1
11.8
5 2 19.56
6 1 11.31
6 2 19.56
7 1 13.43
7 2 22.45
10 1 12.85
10 2 22.45
14 1 14.89
14 2 27.19
19 1 14.36
19 2 27.15
2 1
6.96
2 2 12.08
2 3 17.45
3 1
6.62
3 2 12.08
3 3 17.45

Parameters
U k
opt
2 1
8.63
2 2 14.87
3 1
7.99
3 2 13.17
4 1
9.89
4 2
16.5
5 1
9.89
5 2
16.5
5 1 12.76
5 2
20.5
5 3 30.56
6 1 12.67
6 2
20.5
6 3 30.56

CR
9.44
15.88
9.2
15.71
11.44
18.79
10.37
18.39
12.91
25.73
12.55
25.62
6.25
10.19
15.66
6.05
9.93
15.42

Bilevel
time (s)
3.6
12.7
3.8
24.8
11.8
53.9
6.6
36.4
15.6
15.4
5.3
7.9
3.9
15.1
12.0
2.9
20.7
11.9

CR
7.47
12.29
6.97
11.41
6.65
13.62
6.32
13.44
11.05
17.88
28.14
10.87
17.86
27.9
it
30
67
38
125
82
267
48
195
97
64
35
34
31
103
69
22
116
66

Bilevel
time (s)
0.4
1.3
0.2
1.0
0.9
2.0
0.9
2.8
1.1
5.3
4.8
1.1
8.3
10.0

CR
9.12
16.0
8.92
15.8
11.19
19.47
10.33
18.6
12.64
25.85
12.5
25.68
6.34
10.18
15.57
6.12
9.9
15.29

it
12
27
6
21
24
44
23
55
22
75
48
22
110
90

Cut-set
time (s)
19.2
16.2
7.2
13.8
7.1
12.6
6.0
11.6
4.1
2.2
2.8
1.3
2.1
4.4
4.9
0.1
4.9
2.9

it
470
356
191
301
198
254
169
211
90
39
68
23
41
88
105
2
99
54

CR
7.41
11.95
6.99
11.41
6.13
13.52
5.86
13.19
11.18
18.21
28.32
10.94
17.97
28.04
I
30
31
32
33
34
-

Cut-set
time (s)
0.2
0.6
0.1
0.2
0.2
0.1
0.2
0.1
0.4
0.5
0.3
0.4
0.5
0.2

it
26
52
9
13
20
6
18
6
24
30
14
23
32
12

Parameters
U k
opt
3 1
8.82
3 2 15.18
4 1
8.82
4 2 15.18
6 1 13.37
6 2
21.6
8 1 12.38
8 2 21.41
9 1 11.55
9 2
21.6
12 1
11.5
12 2 21.34
18 1 15.21
18 2 26.64
24 1 15.21
24 2 26.64
29 1 19.02
39 1 19.02

Flow
time (s)
0.1
1.2
0.1
2.0
0.7
8.6
1.2
14.5
1.1
76.6
771.6
1.7
137.9
1548
CR
6.08
10.01
5.49
9.67
11.0
18.72
10.6
18.45
8.36
16.66
8.25
16.52
14.83
26.02
14.76
25.93
17.64
17.33

it
2
6
2
11
19
34
17
41
11
42
59
9
64
50
Bilevel
time (s)
12.6
100.0
17.6
114.9
60.1
120.4
19.9
107.9
11.7
126.5
12.4
79.8
5.8
4.7
5.1
4.5
12.0
8.9

it
70
258
56
243
204
322
94
306
56
264
59
194
25
14
24
13
41
30

CR
5.81
9.97
5.49
9.51
10.71
18.58
10.48
18.28
8.36
16.62
8.19
16.43
14.84
26.15
14.76
26.01
17.53
17.28

Cut-set
time (s)
11.5
88.7
22.4
166.4
130.8
14.9
13.5
21.2
16.5
23.0
9.5
14.2
0.6
0.8
0.7
0.8
7.7
4.7

Table 5: Results on instances with uniform capacities and k 0 = 0
deteriorates the optimal value of the continuous relaxation in both cases, as the gap increases significantly. This could explain why the different formulations are sensitive to the value of k 0 .

21

it
1220
739
331
799
1031
195
206
274
231
254
139
158
8
9
8
9
82
55

Table 5 gives the results for the three formulations in the case of uniform capacities. Each instance
presented in Table 2 has been tested with two different uniform capacities (as previously, those
capacities have been chosen according to the number of terminals, and are equal to 0.8|T | and
0.6|T |). According to these results, the reformulation of the cut-set formulation when capacities
are uniform is particularly interesting, as this formulation does seem to be the best one for this particular case. Furthermore, the solving time is highly reduced in comparison with the non-uniform
case. One can also notice that, in this case, the best continuous relaxation is not always obtained
with the cut-set formulation, as the bilevel formulation often produces one of higher quality.
We also compute the results obtained by the three formulations, without the addition of the valid
inequalities proposed in 3.4, on a subset of instances with k ∈ {1, 2, 3}, k 0 = 0, and non-uniform
B
C
F
capacities. Let ∆time (respectively ∆time and ∆time ) be the mean augmentation of the solving
time when these valid inequalities are removed from the bilevel (respectively cut-set and flow) forB
mulation. On the test instances, ∆time is equal to 3.24 (meaning that the solving time is multiplied
C
F
by 3.24 on average without the valid inequalities), while ∆time and ∆time are equal to 46.78 and
642.94 respectively. Hence, adding these valid inequalities has a huge impact on the solving time,
B
C
especially on the flow and cut-set formulations. Furthermore, let ∆CR (respectively ∆CR ) be the
mean augmentation of the optimal value of the continuous relaxation when these valid inequalities
B
are added to the bilevel (respectively cut-set) formulation. On the test instances, ∆CR is equal
to 1.48 (meaning that the optimal value of the continuous relaxation for the bilevel formulation
C
is multiplied by 1.48 on average with these valid inequalities), while ∆CR is equal to 1.28 (in this
case, when k 0 = 0, the continuous relaxations of the cut-set and flow formulations yield the same
optimal values on this set of instances). The optimal value of the continuous relaxation is then
consequently increased when we add these valid inequalities, especially with the bilevel formulation.
Figure 5 deals with the cost of designing failure-resilient networks; the number of the corresponding test instance is displayed on the x-axis. Each subfigure shows the cost of an optimal solution
for the case where k equals 0 (no arc deleted), 1, 2 and 3. The subfigure (a) corresponds to the
case where k 0 = 0 (no protection allowed), whereas (b), (c) and (d) correspond to the case where
k 0 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.

5

Conclusion

In this paper, we studied the design of robust networks, i.e., networks that are resilient to arc
failures, where one wants to route a uniform flow from a source node to several sink nodes. More
precisely, we first focused on the design of a robust arborescence that minimizes the losses if an
arc failure occurs. We showed that a restriction of the problem is already hard, and then derived
some new mathematical formulations to tackle the problem. Then, we considered the problem of
designing a robust network that is able to route the flow, even after the deletion of any k arcs. We
derived three mathematical formulations for this problem. We finally tested all the methods that
we proposed, and exhibited the associated computational results. The test instances were either
randomly generated or obtained from wind power distribution networks, in which we aim to route
the energy produced by some wind turbines to a substation that will then deliver this energy to
the electrical grid. In a future work, we would like to improve the solving time of our models,
in particular of the bilevel one, for instance by solving the associated subproblems using efficient
heuristics whenever this is possible.

22

30

Cost of the solution

Cost of the solution

40

20

10

0

k=2

k=3

20

10

0

1 2 3 4 5 6 7 8 9 12141115161718202122232425262728

k=1

30

1 2 3 4 5 6 7 8 9 121314111516171819202122242526

k=0

k=1

0

(a) k = 0

k=0

40
Cost of the solution

Cost of the solution

k=3

(b) k0 = 1

40

30

20

10

0

k=2

20

0
1 2 3 4 5 6 7 8 9 101213141115161718192021222526

k=1

k=2

k=3

1 2 3 4 5 6 7 8 9 101213141115161718192021222526

k=1

k=2

k=3

k=0

k=0

(c) k0 = 2

(d) k0 = 3

Figure 5: Cost of the solutions for different instances

References
[1] M. Baïou, AR. Mahjoub, Steiner 2-edge connected subgraph polytopes on series-parallel graphs,
SIAM Journal on Discrete Mathematics, 10-3 (1997) 505-514.
[2] C. Bentz, MC. Costa, A. Hertz, On the edge capacitated Steiner tree problem, CoRR,
abs/1607.07082 (2016).
[3] D. Bienstock, G. Muratore, Strong inequalities for capacitated survivable network design problems, Mathematical Programming, 89-1 (2000) 127-147.
[4] MD. Biha, AR. Mahjoub, Steiner k-edge connected subgraph polyhedra, Journal of Combinatorial Optimization, 4-1 (2000) 131-144.
[5] Q. Botton, B. Fortz, L. Gouveia, M. Poss, Benders decomposition for the hop-constrained
survivable network design problem, INFORMS journal on computing, 25-1 (2013) 13-26.
[6] C. Bousba, L. Wolsey, Finding minimum cost directed trees with demands and capacities,
Annals of operations research, 33-4 (1991) 285-303.
[7] G. Dahl, M. Stoer, A cutting plane algorithm for multicommodity survivable network design
problems, INFORMS Journal on Computing, 10-1 (1998) 1-11.
[8] DZ. Du, JM. Smith, JH. Rubinstein, Advances in Steiner trees (Vol.6), Springer Science &
Business Media, (2013).
23

[9] MR. Garey, DS. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, (1979).
[10] M. Goemans, D. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Mathematical Programming, 60-1-3 (1993) 145-166.
[11] M. Goemans, YS. Myung, A catalog of Steiner tree formulations, Networks, 23-1 (1993) 19-28.
[12] M. Grotschel, CL. Monma, M. Stoer, Design of survivable networks, Handbooks in Operations
Research and Management Science, 7 (1995) 617-672.
[13] A. Hertz, O. Marcotte, A. Mdimagh, M. Carreau, F. Welt, Optimizing the design of a wind
farm collection network, INFOR: Information Systems and Operational Research, 50-2 (2012)
95-104.
[14] FK. Hwang, DS. Richards, P. Winter, The Steiner tree problem, Elsevier, (1992).
[15] H. Kerivin, D. Nace, J. Geffard, Design of survivable networks with a single facility, Universal
Multiservice Networks, 2002. ECUMN 2002. 2nd European Conference on, IEEE (2002) 208218.
[16] H. Kerivin, AR. Mahjoub, Design of survivable networks: A survey, Networks, 46-1 (2005)
1-21.
[17] CH. Papadimitriou, The complexity of the capacitated tree problem, Networks, 8-3 (1978)
217-230.
[18] AC. Pillai, J. Chick, L. Johanning, M. Khorasanchi, V. de Laleu, Offshore wind farm electrical
cable layout optimization, Engineering Optimization, (2015) 1-20.
[19] D. Rajan, A. Atamtürk, A directed cycle-based column-and-cut generation method for capacitated survivable network design, Networks, 43-4 (2004) 201-211.
[20] HD. Ratliff, GT. Sicilia, SH. Lubore, Finding the n most vital links in flow networks, Management Science, 21-5 (1975) 531-539.
[21] M. Stoer, G. Dahl, A polyhedral approach to multicommodity survivable network design, Numerische Mathematik, 68-1 (1994) 149-167.

24

