Implications, conflicts, and reductions for Steiner trees
Mathematical Programming · 2023-02 · 197 (2) · 903-966
DOI: 10.1007/s10107-021-01757-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 30.12.2021. Verfasst von Daniel Rehfeldt und 1 weiteren Autor:innen. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 50 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Bundesministerium für Forschung und Technologie.
Abstract (Originalsprache)
The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot match the state of the art on the vast majority of benchmark instances. The following article seeks to advance exact SPG solution once again. The article is based on a combination of three concepts: Implications, conflicts, and reductions. As a result, various new SPG techniques are conceived. Notably, several of the resulting techniques are (provably) stronger than well-known methods from the literature that are used in exact SPG algorithms. Finally, by integrating the new methods into a branch-and-cut framework, we obtain an exact SPG solver that is not only competitive with, but even outperforms the current state of the art on an extensive collection of benchmark sets. Furthermore, we can solve several instances for the first time to optimality.
Förderung
- Bundesministerium für Forschung und Technologie
Zitieren
APA
Rehfeldt, D., & Koch, T. (2023). Implications, conflicts, and reductions for Steiner trees. Mathematical Programming, 197(2), 903-966. https://doi.org/10.1007/s10107-021-01757-5
Vancouver
Rehfeldt D, Koch T. Implications, conflicts, and reductions for Steiner trees. Mathematical Programming. 2023;197(2):903-966. doi:10.1007/s10107-021-01757-5
BibTeX
@article{Rehfeldt2023,
author = {Rehfeldt, Daniel and Koch, Thorsten},
title = {Implications, conflicts, and reductions for Steiner trees},
journal = {Mathematical Programming},
year = {2023},
volume = {197},
number = {2},
pages = {903--966},
doi = {10.1007/s10107-021-01757-5}
}
EUVIMED