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" [...]


  cash loans . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Cheap Levitra, but also as part of its analogs.