Reduction-based exact solution of prize-collecting Steiner tree problems
From MaRDI portal
Publication:6310076
DOI10.1287/IJOC.2021.1087arXiv1811.09068MaRDI QIDQ6310076FDOQ6310076
Authors: Daniel Rehfeldt, Thorsten Koch 
Publication date: 22 November 2018
Abstract: The prize-collecting Steiner tree problem PCSTP is a well-known generalization of the classical Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the latest (11th) DIMACS Challenge and since then a number of PCSTP solvers have been introduced in the literature, some of which drastically improved on the best results achieved at the Challenge. The following article aims to further advance the state of the art. It introduces new techniques and algorithms for PCSTP, involving various forms of reductions of PCSTP instances to equivalent problems---which for example allows 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, and their profound interaction is described. Finally, the new developments also translate into a strong computational performance: the resulting exact solver outperforms all previous approaches---both in terms of run-time and solvability---and can solve formerly intractable benchmark instances from the 11th DIMACS Challenge to optimality.
This page was built for publication: Reduction-based exact solution of prize-collecting Steiner tree problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6310076)
