Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 5 von 15
Zurück zur Trefferliste

Steiner tree packing revisited

  • The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Nam-Dung Hoang, Thorsten KochORCiD
Dokumentart:Artikel
Titel des übergeordneten Werkes (Englisch):Mathematical Methods of Operations Research
Band:76
Ausgabe / Heft:1
Erste Seite:95
Letzte Seite:123
Jahr der Erstveröffentlichung:2012
Preprint:urn:nbn:de:0297-zib-14625
DOI:https://doi.org/10.1007/s00186-012-0391-8
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.