Optimization Online


A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems

Markus Leitner(markus.leitner***at***univie.ac.at)
Ivana Ljubic(ivana.ljubic***at***essec.edu)
Martin Luipersbeck(martin.luipersbeck***at***univie.ac.at)
Markus Sinnl(markus.sinnl***at***univie.ac.at)

Abstract: In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong's dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful bound-based reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. All tests are applied in every node of the B&B tree. Extensive computational results on benchmark instances for the PCSTP, MWCS and NWSTP indicate the framework's effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner Trees. In many cases the framework even manages to outperform recently proposed state-of-the-art exact and heuristic algorithms. Since the network design problems addressed in this work are frequently used for modeling various real-world applications (e.g., in bioinformatics), the presented B&B framework will also be made publicly available.

Keywords: Steiner Trees, Prize-Collecting Steiner Trees, Dual Ascent, Reduction Tests, Branch-and-Bound

Category 1: Combinatorial Optimization

Category 2: Network Optimization

Category 3: Integer Programming


Download: [PDF]

Entry Submitted: 06/23/2016
Entry Accepted: 06/23/2016
Entry Last Modified: 06/23/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society