Tuesday, 13:15 - 13:40 h, Room: H 3002


Bernd Zey
The stochastic Steiner tree problem: Models and solution strategies

Coauthors: Immanuel Bomze, Markus Chimani, Michael J√ľnger, Ivana Ljubic, Petra Mutzel


We consider the Steiner tree problem under a two-stage stochastic model with fixed recourse and finitely many scenarios. Thereby, edges are bought in the first stage when only probabilistic information on future edge costs and the set of terminals is known. In the second stage, one scenario is realized and additional edges are purchased to connect the now known set of terminals. The goal is to buy profitable edges in the first stage such that the overall expected costs are minimized, i.e., the sum of the first and expected second stage costs.
We discuss the strength of undirected, semi-directed, and directed cut-set based integer programming models with binary first and second stage variables. To solve this NP-hard problem to optimality, we suggest a branch-and-cut approach based on Benders decomposition and the derived Integer-L-shaped algorithm. By a simple modification of the optimal dual solution of the subproblems we show how to improve the generated optimality Cuts which reduce the running time significantly. In our experiments we compare the extended formulation and the decomposition of the different models computationally.


Talk 1 of the invited session Tue.2.H 3002
"Tree problems" [...]
Cluster 23
"Telecommunications & networks" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.