Optimization Online


On the exact solution of prize-collecting Steiner tree problems

Daniel Rehfeldt(rehfeldt***at***zib.de)
Thorsten Koch(koch***at***zib.de)

Abstract: The prize-collecting Steiner tree problem (PCSTP) is a well-known generalization of the classic Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the 11th DIMACS Challenge in 2014, and since then, several PCSTP solvers have been introduced in the literature. Although these new solvers further, and often drastically, improved on the results of the DIMACS Challenge, many PCSTP instances have remained unsolved. The following article describes further advances in the state of the art in exact PCSTP solving. It introduces new techniques and algorithms for PCSTP , involving various new transformations (or reductions) of PCSTP instances to equivalent problems; for example to decrease the problem size or to obtain a better IP formulation. Several of the new techniques and algorithms provably dominate previous approaches. Further theoretical properties of the new components, such as their complexity, are discussed. Moreover, new complexity results for the exact solution of PCSTP and related problems are given, which form the base of the algorithmic developments. Finally, the new developments also translate into a strong computational performance: the resulting exact PCSTP solver outperforms all previous approaches, both in terms of run-time and solvability. In particular, it solves several formerly intractable benchmark instances from the 11th DIMACS Challenge to optimality. Moreover, several recently introduced large-scale instances with up to 10 million edges, previously considered to be too large for any exact approach, can now be solved to optimality in less than two hours.

Keywords: prize-collecting Steiner tree

Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 04/12/2020
Entry Accepted: 04/16/2020
Entry Last Modified: 04/12/2020

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