6469
eng
reportzib
0
--
2017-07-25
--
Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver.
The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
1438-0064
urn:nbn:de:0297-zib-64699
10.1137/17M1145963
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
17-45
eng
uncontrolled
maximum-weight connected subgraph
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6469/mwcs_zib_revision.pdf