5977
eng
reportzib
0
--
2016-01-07
--
Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
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 paper 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, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.
1438-0064
urn:nbn:de:0297-zib-59777
10.4208/jcm.1709-m2017-0002
Appeared in: Journal of Computational Mathematics, 36(3):459-468, 2018
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
16-36
eng
uncontrolled
graph transformation
eng
uncontrolled
Steiner tree problems
eng
uncontrolled
prize-collecting Steiner tree problem
eng
uncontrolled
maximum-weight connected subgraph problem
COMBINATORICS (For finite fields, see 11Txx)
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5977/pcmwtransformations.pdf