Abstract
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 employing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Achterberg T, Raack C (2010) The MCF-separator—detecting and exploiting multi-commodity flows in MIPs. Math Program C, pp 125–165
Balas E, Martin C (1980) Pivot and complement—a heuristic for 0/1 programming. Manag Sci 26: 86–96
Balas E, Schmietab S, Wallacea C (2004) Pivot and shift—a mixed integer programming heuristic. Discret Optim 1: 3–12
Boit C (2004) Personal communication
Brady ML, Brown DJ (1984) VLSI routing: four layers suffice. In: Preparata FP (ed) Advances in computing research: VLSI theory. Jai Press, London, pp 245–258
Burstein M, Pelavin R (1983) Hierachical wire routing. IEEE Trans Computer Aided Des 2: 223–234
Chopra S (1994) Comparison of formulations and a heuristic for packing Steiner trees in a graph. Ann Oper Res 50: 143–171
Coohoon JP, Heck PL (1988) BEAVER: a computational-geometry-based tool for switchbox routing. IEEE Trans Comput Aided Des 7: 684–697
Grötschel M, Jünger M, Reinelt G (1989) Via minimization with pin preassignments and layer preference. Zeitschrift für Angewandte Mathematik und Mechanik 69: 393–399
Grötschel M, Martin A, Weismantel R (1996) Packing steiner trees: a cutting plane algorithm and computational results. Math. Program 72: 125–145
Grötschel M, Martin A, Weismantel R (1996) Packing steiner trees: further facets. Eur J Comb 17: 39–52
Grötschel M, Martin A, Weismantel R (1996) Packing steiner trees: polyhedral investigations. Math Program 72: 101–123
Grötschel M, Martin A, Weismantel R (1997) The steiner tree packing problem in VLSI design. Math Program 78: 265–281
Held S, Korte B, Rautenbach D, Vygen J (2011) Combinatorial optimization in VLSI design. In: Chvátal V (ed) Combinatorial optimization—methods and applications, vol 31 of NATO science for peace and security series—D: information and communication security, pp 33–96
Jørgensen DG, Meyling M (2000) Application of column generation techniques in VLSI design. Master’s thesis, Department of Computer Science, University of Copenhagen
Jünger M, Martin A, Reinelt G, Weismantel R (1994) Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits. Math Program 63: 257–279
Koch T ZIMPL. http://zimpl.zib.de
Koch T, Martin A (1998) Solving steiner tree problems in graphs to optimality. Networks 32: 207–232
Korte B, Prömel H-J, Steger A (1990) Steiner trees in VLSI-layout. In: Korte B, Lovász L, Prömel H-J, Schrijver A (eds) Paths, flows, and VLSI-layout. Springer, Berlin
Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Wiley, London
Lipski W (1984) On the structure of three-layer wireable layouts. In: Preparata FP (ed) Advances in computing research: VLSI theory. Jai Press, Wiley, London, pp 231–244
Luk WK (1985) A greedy switch-box router. Integration 3: 129–149
Martin A (1992) Packen von Steinerbäumen: Polyedrische Studien und Anwendungen. PhD thesis, Technische Universität Berlin
Polzin T (2003) Algorithms for the steiner problem in networks. PhD thesis, Universität des Saarlandes
Raack C, Koster AMCA, Orlowski S, Wessly R (2011) On cut-based inequalities for capacitated network design polyhedra. Networks 57: 141–156
Wong RT (1984) A dual ascent approach for steiner tree problems on a directed graph. Math Program 28: 271–287
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the first author is supported by NAFOSTED.
Rights and permissions
About this article
Cite this article
Hoàng, ND., Koch, T. Steiner tree packing revisited. Math Meth Oper Res 76, 95–123 (2012). https://doi.org/10.1007/s00186-012-0391-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-012-0391-8