Steiner Tree Packing Revisited

Please always quote using this URN: urn:nbn:de:0297-zib-14625
  • 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.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Nam-Dung Hoang, Thorsten Koch
Document Type:ZIB-Report
Tag:Integer Programming; Steiner tree packing; grid graphs
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Date of first Publication:2012/01/27
Series (Serial Number):ZIB-Report (12-02)
ISSN:1438-0064
Published in:Appeared in: Mathematical Methods of Operations Research August 2012, Volume 76, Issue 1, pp 95-123
DOI:http://dx.doi.org/10.1007/s00186-012-0391-8
Licence (German):License LogoCreative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung

$Rev: 13581 $