A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems

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.