TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Pajor, Thomas
A1  - Uchoa, Eduardo
A1  - Werneck, Renato F.
T1  - A robust and scalable algorithm for the Steiner problem in graphs
JF  - Mathematical Programming Computation
N2  - We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branch-and-bound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
AB  - We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branch-and-bound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
KW  - Software
KW  - Theoretical Computer Science
Y1  - 2017
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-017-0123-4
DO  - https://doi.org/10.1007/s12532-017-0123-4
VL  - 10
IS  - 1
SP  - 69
EP  - 118
S1  - 50
PB  - Springer Science and Business Media LLC
ER  -