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

[img]
Preview
PDF
zaik2010-602.pdf

Download (291kB) | Preview

Abstract

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.

Item Type: Book Section, Proceedings Item or annotation in a legal commentary
Creators:
CreatorsEmailORCIDORCID Put Code
Bomze, ImmanuelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Chimani, MarkusUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Ljubic, IvanaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
Zey, BerndUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-549965
Title of Book: ISAAC 2010, Part I
Series Name: LNCS
Volume: 6506
Page Range: pp. 427-439
Date: 2011
Publisher: Springer-Verlag
Place of Publication: Heidelberg
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54996

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item