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.

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.


Actions:
Download: [img] PDF - Accepted Version
Download (291kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: [error in script] 0 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 90-XX Operations research, mathematical programming > 90-08 Computational methods

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C08 Special problems of linear programming (transportation, multi-index, etc.)

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

  • Uncontrolled Keywords: stochastic Steiner tree, stochastic integer programming, branch-and-cut, Benders decomposition
    Subjects: 90-XX Operations research, mathematical programming > 90-08 Computational methods
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C08 Special problems of linear programming (transportation, multi-index, etc.)
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 14 Mar 2011 00:00
    Last Modified: 09 Jan 2012 11:59
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 14 Mar 2011 00:00
    Last Modified: 09 Jan 2012 11:59
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/602