You are here:: TU Dortmund > Department of Computer Science > Chair 11: ALGORITHM ENGINEERING > Staff > Dr. Bernd Zey > The Stochastic Survivable Network Design Problem
 

Table of Contents

The Stochastic Survivable Network Design Problem

This page contains further informations and benchmark data for the Stochastic Survivable Network Design Problem (SSNDP) and our work on this topic:

or the related technical report

Problem Definition

The deterministic survivable network design problem (NDP) is defined as follows: Given is an undirected graph $G=(V,E)$, edge costs $c_e$, and a $|V|\times |V|$ matrix $r$ defining the edge connectivity requirements. The objective consists of finding a set of edges $E' \subseteq E$ such that there exist at least $r_{ij}$ edge disjoint path between vertice $i$ and $j$, $\forall i\not=j$, with minimum costs, i.e., $\min \sum_{e \in E'} c_e$.

Here, we consider the two-stage stochastic survivable network design problem (SSNDP) with fixed recourse and finitely many scenarios in which the edge requirements and the edge costs are subject to uncertainty. This means there are two points in times (also called stages): In the first stage (now, on Monday), we only have probabilistic information in terms of possible outcomes (scenarios) in the future (second stage, on Tuesday).

A scenario $k$ thereby specifies edge requirements $r_{ij}^k$, edge costs $c_e^k$, and a probability $p^k$ for it to be realized. Expected edge costs in the second stage are higher and based on these informations, we may buy some edges at a lower price now and in the second stage, when one of the given scenarios is realized, we have to purchase additional edges in order to satisfy the connectivity requirements.

The goal is to make a decision about edges to be purchased in the first stage while minimizing the expected cost of the full solution (i.e., after the second stage). More formally, let $E^0$ be the selected first-stage edges and $E^k$ the edges of the $k$th scenario. Then the objective is $\min \sum_{e \in E^0} c_e^0 + \sum_k p^k \sum_{e \in E^k} c_e^k$.

Instances

Generation

Deterministic instances were generated by adopting the idea of Johnson, Minkoff, and Phillips (D. S. Johnson, M. Minkoff, and S. Phillips. The prize-collecting Steiner tree problem: Theory and practice. In ACM-SIAM SODA, pages 760-–769. SIAM, 2000), for the prize-collecting Steiner tree problem, which is frequently used as benchmark in the network design community. After randomly distributing $n\in \{30,50,75\}$ points in the unit square, a minimum spanning tree is computed using the points as nodes and the Euclidean distances between all vertex pairs as edge costs. To generate only feasible instances we augmented this tree by inserting edges between leaves which are adjacent in the planar embedding.

The resulting biconnected graph is extended by adding all edges for which the Euclidean distance is less than or equal to $1.6\alpha/\sqrt{n}$. We have introduced $\alpha$ in order to control the density of the graph. (The original parameter used by Johnson, Minkoff, and Phillips was $1.6$ and corresponds to $\alpha=1$ in our setting). In our experiments we use $\alpha = 0.9$ which led to graphs with average density $2.07$. The edge-connectivity requirements are set as follows. We have randomly drawn $\rho\%$ of the nodes as base sets of $\cR_1$ and $\cR_2$ customers. Here, we use $\rho= 40$ and we additionally introduce a random root node that is contained in $\cR_2$. An example is given in Figures below.

To transform these instances into stochastic ones we randomly and independently generate $\bar k$ scenarios. The probabilities are set by randomly distributing $10,000$ points over the scenarios, where each point corresponds to a probability of $0.01\%$. Edge costs $c^0$ in the first stage are Euclidean distances and in the second stage for each edge $e$ and scenario $k \in \cK$ randomly drawn from the interval $[1.1c_e^0, 1.3c_e^0]$. Edge-connectivity requirements are generated by randomly drawing $\rho^k\%$ from the vertex sets $\cR_1$ and $\cR_2$ each as $\cR_1^k$ and $\cR_2^k$ customers, respectively, for scenario $k$. Here, we use $\rho^k= 30$ for all scenarios $k$. The special root node was set to be an $\cR_2^k$ node in each scenario $k$.

For each deterministic instance we generated a stochastic instance with $\bar k = 1000$ scenarios and took the first $k$ to obtain an SSNDP instance for $k$ scenarios\footnote; We used 14 values for $k$: $k\in \{5,10,20,50,75,100,150,200,250,300,400,500,750,1000\}$. Probabilities for the scenarios of the instances with $k < 1000$ are scaled appropriately. Overall, we generated 20 graphs for each $n\in\{30, 50, 75\}$ and $k$ leading to 840 instances which can be downloaded in the Download section.

Generated graph with MST (solid lines) and biconnectivity augmentation edges (dashed lines) Final instance with root (red diamond) R1 (green) and R2 (blue) nodes

File format

Each file has the same structure and consists of 5 important parts

  • general: number of scenarios and id of the root node (if there is a root node)
  • probabilities: the probabilities for each scenario which should sum up to 1
  • node: each line represents a node with the following informations:
    • identifier (normally starts at 1)
    • x- and y-coordinate (for drawing purposes only)
  • link: each line represents an edge with the following informations:
    • identifier (normally starts at 1)
    • identifier of the source and target node
    • a ($K+1$)-vector with the weights for this edge in the first stage and each scenario
  • connectivity: each line contains the list of nodes in $R_1$ or $R_2$, respectively, for each scenario:
    • scenario id (normally starts at 0 (not consistent with other ids - sorry!)
    • 1 (x)or 2: indicates wether the list of nodes are $R_1$ or $R_2$ nodes
    • the size of $R_i$
    • the list of the $|R_i|$ vertices

All values are separated by a tabulator (“\t”).

Lines starting with a “#” are comments. In general, each file starts with some informations about the deterministic instance, the probability distribution, etc.

Example: 

# automatically generated file (type G) 
# (type G: random points in unit square + MST + edge=(i,j) iff distance(i,j) < alpha/sqrt(n)) 
# 20 nodes, 44 edges 
# parameters: 
# alpha=0.90000 
# nr Scenarios=5 
# distribution=equal 
# probability(R2)=42, probability(R1)=41 
# scenario-probability(R2)=32, scenario-probability(R1)=31 
# edge-costs in [1.1000c_e, 1.3000c_e] 
general 
# nr scenarios | root node (if given) 
5	1 
probabilities 
# probability for each scenario (p_k) 
0.15310	0.23660	0.20280	0.21270	0.19480 
node 
#id	x	y 
1	745.01	619.98 
2	703.93	329.02 
3	631.63	468.01 
<etc.> 
link 
# id	| source | target | weight 1st stage | weight Scenario 1 | weight Scenario 2 | ... 
1	1	2	293.00	327.00	365.00	362.00	327.00	370.00 
2	1	3	189.00	236.00	230.00	215.00	218.00	217.00 
<etc.> 
connectivity 
#scenario	R_1 or R_2	|R_i|	list of nodes in R_i 
0	1	3	11	13	18 
0	2	2	1	2 
1	1	2	15	16 
1	2	2	1	6 
2	1	3	10	12	16 
2	2	2	1	5

Downloads

  • SSNDP instances: n=30, n=50, n=75
  • GML files for SSNDP instances: n=30, n=50, n=75,
  • The red vertex is the root node which is an $R_2$-node in each scenario. The green and blue vertices are potential $R_2$ and $R_1$ vertices, respectively.

Results

Some results (5 out of 20 instances) for the 50-vertices instances can be found in the following table.

instance2-stage branch&cut2-stage branch&cut (Magnanti-Wong)2-stage branch&cut (strengthened cuts)Deterministic Equivalent
nameeKOPTUBt[s]iter. Masterb&bLP rootgapUBt[s]iter. Masterb&bLP rootgapUBt[s]iter. Masterb&bLP rootgapUBt[s]b&bLP rootgap
g-50-103-19-22-0.75–30-30–10-30–5s.ssndp10354658,944658,947,06411414658,9404658,942,42226,614658,9404658,941,3083614658,9404658,940,23414658,940
g-50-103-19-22-0.75–30-30–10-30–10s.ssndp103104866,084866,0842,718101414861,02<0,014866,0817,11423,637,84861,02<0,014866,088,94433434861,02<0,014866,081,34834861,02<0,01
g-50-103-19-22-0.75–30-30–10-30–20s.ssndp103204747,744747,7438,34669114738,26<0,014747,7416,76819,6114738,26<0,014747,749,07226114738,26<0,014747,7414,45274738,26<0,01
g-50-103-19-22-0.75–30-30–10-30–50s.ssndp103504602,324602,32115,77454174594,94<0,014602,3255,30816,2174594,94<0,014602,3233,6723174594,94<0,014602,32206,026694594,94<0,01
g-50-103-19-22-0.75–30-30–10-30–75s.ssndp103754593,54593,575,515174589,94<0,014593,551,18217,874589,94<0,014593,524,2222274589,94<0,014593,5876,9481834589,94<0,01
g-50-103-19-22-0.75–30-30–10-30–100s.ssndp1031004609,854609,85160,9884394608,01<0,014609,8571,24216,494608,01<0,014609,8536,5782094608,01<0,014609,85720010434608,01<0,01
g-50-103-19-22-0.75–30-30–10-30–150s.ssndp1031504600,044600,04240,8683874597,76<0,014600,04108,4541474597,76<0,014600,0494,4581874597,76<0,01-7200367,44597,76-
g-50-103-19-22-0.75–30-30–10-30–200s.ssndp1032004607,584607,58358,34234134605,18<0,014607,58193,27414,4134605,18<0,014607,58127,81616134605,18<0,01-7200138,24605,18-
g-50-103-19-22-0.75–30-30–10-30–250s.ssndp1032504642,64642,6365,13436114639,57<0,014642,6246,26813,8114639,57<0,014642,6115,43817114639,57<0,01-720077,44639,57-
g-50-105-16-27-0.75–30-30–10-30–5s.ssndp10554486,624486,628,47813714486,6204486,623,90438,814486,6204486,622,2885314486,6204486,620,35814486,620
g-50-105-16-27-0.75–30-30–10-30–10s.ssndp105104408,824408,8211,0948434408,35<0,014408,825,472534408,35<0,014408,822,9883334408,35<0,014408,831,63834408,35<0,01
g-50-105-16-27-0.75–30-30–10-30–20s.ssndp105204660,714660,7128,22466114658,71<0,014660,7117,73822,4114658,71<0,014660,719,2130114658,71<0,014660,7114,46154658,71<0,01
g-50-105-16-27-0.75–30-30–10-30–50s.ssndp105504621,094621,0935,44354619,11<0,014621,0920,371454619,11<0,014621,0911,0541754619,11<0,014621,09147,772414619,11<0,01
g-50-105-16-27-0.75–30-30–10-30–75s.ssndp105754598,974598,9753,874294598,37<0,014598,9741,77815,894598,37<0,014598,9721,2542194598,37<0,014598,97115,13294598,37<0,01
g-50-105-16-27-0.75–30-30–10-30–100s.ssndp1051004607,84607,872,6584054606,4<0,014607,848,80614,654606,4<0,014607,822,381654606,4<0,014607,8902,77714606,4<0,01
g-50-105-16-27-0.75–30-30–10-30–150s.ssndp1051504729,894729,8993,4243834729,39<0,014729,8957,40414,834729,39<0,014729,8933,091734729,39<0,014729,89513,154729,39<0,01
g-50-105-16-27-0.75–30-30–10-30–200s.ssndp1052004727,64727,6127,3123734727,1<0,014727,679,5821534727,1<0,014727,642,3661734727,1<0,014727,61301,14434727,1<0,01
g-50-105-16-27-0.75–30-30–10-30–250s.ssndp1052504745,264745,26168,6543734745,02<0,014745,26101,92214,834745,02<0,014745,2653,1981734745,02<0,014745,262399,2134745,02<0,01
g-50-110-29-14-0.75–30-30–10-30–5s.ssndp11053970,783970,788,72212313970,7803970,783,44434,813970,7803970,781,7564113970,7803970,780,2113970,780
g-50-110-29-14-0.75–30-30–10-30–10s.ssndp110104022,784022,7812,8369314022,7804022,784,01221,814022,7804022,781,9182514022,7804022,780,84814022,780
g-50-110-29-14-0.75–30-30–10-30–20s.ssndp110204354,774354,7742,32482114349,91<0,014354,7721,72828,2114349,91<0,014354,7710,0231114349,91<0,014354,778,5554349,91<0,01
g-50-110-29-14-0.75–30-30–10-30–50s.ssndp110504143,134143,1348,315054138,57<0,014143,1326,60816,254138,57<0,014143,1311,571854138,57<0,014143,1334,49254138,57<0,01
g-50-110-29-14-0.75–30-30–10-30–75s.ssndp110754128,374128,3762,814934127,13<0,014128,3730,59816,834127,13<0,014128,3715,0421934127,13<0,014128,371652,2822714127,13<0,01
g-50-110-29-14-0.75–30-30–10-30–100s.ssndp1101004117,534117,5397,2324554112,51<0,014117,5347,46814,454112,51<0,014117,5322,991754112,51<0,014117,535414,5964894112,51<0,01
g-50-110-29-14-0.75–30-30–10-30–150s.ssndp1101504122,874122,87142,1884354118,6<0,014122,8773,89214,654118,6<0,014122,8735,0161754118,6<0,01-7200325,44118,6-
g-50-110-29-14-0.75–30-30–10-30–200s.ssndp1102004129,474129,47234,1383994121,33<0,014129,47139,3021494121,33<0,014129,4762,7921694121,33<0,01-7200117,44121,33-
g-50-110-29-14-0.75–30-30–10-30–250s.ssndp1102504145,474145,47283,3983874138,25<0,014145,47169,33414,274138,25<0,014145,4772,0321674138,25<0,01-720075,44138,25-
g-50-119-16-23-0.75–30-30–10-30–5s.ssndp11954728,914728,9114,51813634728,51<0,014728,914,73231,234728,51<0,014728,913,2164434728,51<0,014728,910,55434728,51<0,01
g-50-119-16-23-0.75–30-30–10-30–10s.ssndp119104744,974744,9752,35240114694,430,0114744,9734,3535,6114694,430,0114744,9717,06243114694,430,0114744,9713,45254694,430,011
g-50-119-16-23-0.75–30-30–10-30–20s.ssndp119204758,294758,2959,8980154739,47<0,014758,2934,72426,4154739,47<0,014758,2917,09634154739,47<0,014758,2946,822314739,47<0,01
g-50-119-16-23-0.75–30-30–10-30–50s.ssndp119504827,794827,7990,4325334826,49<0,014827,7933,9181834826,49<0,014827,7923,4182334826,49<0,014827,79204,652194826,49<0,01
g-50-119-16-23-0.75–30-30–10-30–75s.ssndp119754868,244868,24121,1744674859,7<0,014868,2465,59216,874859,7<0,014868,2437,5421874859,7<0,014868,24945,546594859,7<0,01
g-50-119-16-23-0.75–30-30–10-30–100s.ssndp1191004870,244870,24157,2364474864,13<0,014870,2495,216,474864,13<0,014870,2452,232074864,13<0,014870,243435,4461814864,13<0,01
g-50-119-16-23-0.75–30-30–10-30–150s.ssndp1191504916,184916,18268,314354910,75<0,014916,18153,5114,854910,75<0,014916,1877,6781754910,75<0,01-7200178,24910,75-
g-50-119-16-23-0.75–30-30–10-30–200s.ssndp1192004899,864899,86283,9884134898,57<0,014899,86132,4914,834898,57<0,014899,8677,6761634898,57<0,01-7200254898,57-
g-50-119-16-23-0.75–30-30–10-30–250s.ssndp1192504907,034907,03615,023854905,16<0,014907,03222,0661434905,16<0,014907,03115,3421634905,16<0,01-72001--
g-50-123-24-18-0.75–30-30–10-30–5s.ssndp12355159,495159,4931,31432895149,51<0,015159,4912,07257,210,25149,51<0,015159,496,4087795149,51<0,015159,491,538135149,51<0,01
g-50-123-24-18-0.75–30-30–10-30–10s.ssndp123104794,934794,9325,12412174790,5<0,014794,9310,85228,274790,5<0,014794,935,233574790,5<0,014794,932,72674790,5<0,01
g-50-123-24-18-0.75–30-30–10-30–20s.ssndp123204977,584977,5870,04181114969,57<0,014977,5829,86426,8114969,57<0,014977,5815,99831114969,57<0,014977,5898,4361014969,57<0,01
g-50-123-24-18-0.75–30-30–10-30–50s.ssndp123504862,664862,66325,148271314858,03<0,014862,66103,66621,2294858,03<0,014862,6643,8223294858,03<0,014862,662954,0486914858,03<0,01
g-50-123-24-18-0.75–30-30–10-30–75s.ssndp123754775,094775,09166,21101114773,38<0,014775,0981,66819,412,64773,38<0,014775,0936,08622114773,38<0,014775,092501,892714773,38<0,01
g-50-123-24-18-0.75–30-30–10-30–100s.ssndp1231004798,764798,76161,2485254797,8<0,014798,7663,78817,654797,8<0,014798,7646,891854797,8<0,014798,767091,1423594797,8<0,01
g-50-123-24-18-0.75–30-30–10-30–150s.ssndp1231504879,054879,051076,024195174875,8<0,014879,05202,58417,2154875,8<0,014879,0585,06420174875,8<0,01-7200188,24875,8-
g-50-123-24-18-0.75–30-30–10-30–200s.ssndp1232004893,474893,47876,91649194889,36<0,014893,47323,7761715,84889,36<0,014893,47131,93618194889,36<0,01-720061,44889,36-
g-50-123-24-18-0.75–30-30–10-30–250s.ssndp1232504860,854860,851500,892101194858,03<0,014860,85427,46616,8174858,03<0,014860,85140,81219154858,03<0,01-720021,44858,03-

description:

  • e: the number of edges
  • OPT: the optimum solution
  • UB: best found solution (Upper Bound)
  • t[s]: the running time in seconds
  • b&b: the number of branch&bound nodes
  • LP root: lp-value of the problem in the root node
  • gap = (UB-LP)/UB
  • iter. Master: iterations of the master in the 2-stage branch&cut algorithm

Example

Below one can see two scenarios of an optimum solution of an instance with 50 vertices and 5 scenarios (g-50-101-5scenarios). The solid lines are the edges bought in the first stage, the dashed lines depict the edges of the scenario. The red vertex is the root node, the green vertices are $R_2$ and the blue vertices $R_1$ nodes, respectively, of the scenario.

As one can easily see, the first stage is disconnected.

Optimum solution scenario 0, instance g-50-101-5scenarios Optimum solution scenario 1, instance g-50-101-5scenarios

The images are generated by storing the solution as .gml file, loading it with yEd, and exporting it as a .png.

 
Last modified: 2017-06-13 11:19 (external edit)
DokuWiki — RSS-Feed —
Barrierefreiheit   Datenschutzerklärung   Impressum