Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut

Bomze, Immanuel and Chimani, Markus and Jünger, Michael and Ljubic, Ivana and Mutzel, Petra and Zey, Bernd (2011) Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut.
Published In: ISAAC 2010, Part I, LNCS. 6506 Springer-Verlag 2011, pp. 427-439.


We consider the Steiner tree problem under a two-stage stochastic model with recourse and finitely many scenarios. In this prob- lem, edges are purchased in the first stage when only probabilistic infor- mation on the set of terminals and the future edge costs is known. In the second stage, one of the given scenarios is realized and additional edges are puchased in order to interconnect the set of (now known) ter- minals. The goal is to decide on the set of edges to be purchased in the first stage while minimizing the overall expected cost of the solution. We provide a new semi-directed cut-set based integer programming formula- tion, which is stronger than the previously known undirected model. We suggest a two-stage branch-and-cut (B&C) approach in which L-shaped and integer-L-shaped cuts are generated. In our computational study we compare the performance of two variants of our algorithm with that of a B&C algorithm for the extensive form of the deterministic equiva- lent (EF). We show that, as the number of scenarios increases, the new approach significantly outperforms the (EF) approach.

Download: [img] PDF - Accepted Version
Download (291kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-602
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 14 Mar 2011 00:00
Last Modified: 09 Jan 2012 11:59