Decomposition methods for the two-stage stochastic Steiner tree problem

Markus Leitner (), Ivana Ljubić (), Martin Luipersbeck () and Markus Sinnl ()
Additional contact information
Markus Leitner: University of Vienna, Department of Statistics and Operations Research, Faculty of Business, Economics and Statistics
Ivana Ljubić: ESSEC Business School of Paris
Martin Luipersbeck: University of Vienna, Department of Statistics and Operations Research, Faculty of Business, Economics and Statistics
Markus Sinnl: University of Vienna, Department of Statistics and Operations Research, Faculty of Business, Economics and Statistics

Computational Optimization and Applications, 2018, vol. 69, issue 3, No 6, 713-752

Abstract: Abstract A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances. The effectiveness of our method is compared in an extensive computational study with the state-of-the-art exact approach, which employs a Benders decomposition based on two-stage branch-and-cut, and a genetic algorithm introduced during the DIMACS implementation challenge on Steiner trees. Our results indicate that the presented method significantly outperforms existing ones, both on benchmark instances from literature, as well as on large-scale telecommunication networks.

Keywords: Lagrangian relaxation; Benders decomposition; Stochastic optimization; Steiner trees (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-017-9966-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:69:y:2018:i:3:d:10.1007_s10589-017-9966-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-017-9966-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().