Universität zu Köln

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.

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:	Creators Email ORCID ORCID Put Code Bomze, Immanuel UNSPECIFIED UNSPECIFIED UNSPECIFIED Chimani, Markus UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Ljubic, Ivana UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED Zey, Bernd UNSPECIFIED UNSPECIFIED UNSPECIFIED
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