On the exact solution of prize-collecting Steiner tree problems

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.

Article

Download

View On the exact solution of prize-collecting Steiner tree problems