Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
Year: 2018
Author: Daniel Rehfeldt, Thorsten Koch
Journal of Computational Mathematics, Vol. 36 (2018), Iss. 3 : pp. 459–468
Abstract
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this article transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, the considerable implications for practical solving approaches will be demonstrated, including the computation of strong upper and lower bounds.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1709-m2017-0002
Journal of Computational Mathematics, Vol. 36 (2018), Iss. 3 : pp. 459–468
Published online: 2018-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 10
Keywords: Prize-collecting Steiner tree problem Maximum-weight connected subgraph problem Graph transformations Dual-ascent heuristics.
Author Details
-
Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
Rehfeldt, Daniel | Koch, ThorstenSIAM Journal on Optimization, Vol. 29 (2019), Iss. 1 P.369
https://doi.org/10.1137/17M1145963 [Citations: 14] -
On the Exact Solution of Prize-Collecting Steiner Tree Problems
Rehfeldt, Daniel | Koch, ThorstenINFORMS Journal on Computing, Vol. 34 (2022), Iss. 2 P.872
https://doi.org/10.1287/ijoc.2021.1087 [Citations: 6] -
Modeling, Simulation and Optimization of Complex Processes HPSC 2018
SCIP-Jack: An Exact High Performance Solver for Steiner Tree Problems in Graphs and Related Problems
Rehfeldt, Daniel | Shinano, Yuji | Koch, Thorsten2021
https://doi.org/10.1007/978-3-030-55240-4_10 [Citations: 3] -
Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores
Shinano, Yuji | Rehfeldt, Daniel | Koch, Thorsten2019
https://doi.org/10.1007/978-3-030-19212-9_35 [Citations: 6]