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.
|
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: |
|
||||||||||||||||||||||||||||
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 |