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 (2010) Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut.
Technical Report , 13 p.

Abstract

We consider the Steiner tree problem under a two-stage stochastic model with recourse and finitely many scenarios. In this problem, edges are purchased in the first stage when only probabilistic information 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 purchased in order to interconnect the set of (now known) terminals. 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 formulation, 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 equivalent (EF). We show that, as the number of scenarios increases, the new approach significantly outperforms the (EF) approach.


Actions:
Download: [img] PDF
Download (291kB)
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords:
Subjects:
  • 68-XX Computer science > 68Wxx Algorithms > 68W01 General

  • Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    ZAIK Number: UNSPECIFIED
    Depositing User: Archive Admin
    Date Deposited: 07 Jan 2011 10:10
    Last Modified: 04 Jul 2014 09:40
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/848