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

M. Leitner, Ivana Ljubic, Martin Luipersbeck, Markus Sinnl

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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 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. 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. Moreover, results on new asymmetric instances for the APCSTP are reported. Since the addressed network design problems are frequently used for modeling various real-world applications (e.g., in bioinformatics), the implementation of the presented B&B framework has been made publicly available.
Original languageEnglish
Pages (from-to)217-420
Number of pages19
JournalINFORMS Journal on Computing
Volume30
Issue number2
DOIs
Publication statusPublished - 2018

Keywords

  • Branch-and-bound
  • Dual ascent
  • Prize-collecting Steiner trees
  • Reduction techniques
  • Steiner trees

Fingerprint Dive into the research topics of 'A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems'. Together they form a unique fingerprint.

Cite this