EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Implications, conflicts, and reductions for Steiner trees

Daniel Rehfeldt, Thorsten Koch

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →