×

zbMATH — the first resource for mathematics

The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets. (English) Zbl 0821.90124
Summary: We give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP- relaxation of the undirected one.

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A.V. Aho, M.R. Garey and F.K. Hwang, ”Rectilinear Steiner trees: Efficient special case algorithms,”Networks 7 (1977) 37–58. · Zbl 0351.05102 · doi:10.1002/net.3230070104
[2] Y.P. Aneja, ”An integer linear programming approach to the Steiner problem in graphs,”Networks 10 (1980) 167–168. · Zbl 0445.90087 · doi:10.1002/net.3230100207
[3] A. Bachem and M. Grötschel, ”New aspects of polyhedral theory” in:Modern Applied Mathematics: Optimization and Operations Research (North-Holland, Amsterdam, 1982) 51–106.
[4] E. Balas and W. Pulleyblank, ”The perfectly matchable subgraph polytope of a bipartite graph,”Networks 13 (1983) 495–516. · Zbl 0525.90069 · doi:10.1002/net.3230130405
[5] M. Ball, W. Liu and W. Pulleyblank, ”Two-terminal Steiner tree polyhedra,” preprint (1988).
[6] S. Chopra, ”On the spanning tree polyhedron,”Operations Research Letters 8 (1989) 25–29. · Zbl 0675.90060 · doi:10.1016/0167-6377(89)90029-1
[7] S. Chopra and M.R. Rao, ”The Steiner tree problem I: Formulations, compositions and extensions of facets,” New York University Research Report No. 88-82, (1988).
[8] S. Chopra, E. Gorres and M.R. Rao, ”Solving a Steiner tree problem on a graph using branch and cut,”ORSA Journal on Computing 4(3) (1982) 320–335. · Zbl 0759.90091
[9] G. Cornuejols, J. Fonlupt and D. Naddef, ”The travelling salesman problem on a graph and some related integer polyhedra,”Mathematical Programming 33 (1985) 1–27. · Zbl 0562.90095 · doi:10.1007/BF01582008
[10] S.E. Dreyfus and R.A. Wagner, ”The Steiner problem in graph,”Networks 1 (1972) 195–207. · Zbl 0229.05125 · doi:10.1002/net.3230010302
[11] D.R. Fulkerson, ”Blocking and anti-blocking pairs of polyhedra,”Mathematical Programming 1 (1971) 168–194. · Zbl 0254.90054 · doi:10.1007/BF01584085
[12] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to Theory of NP-completeness (W.H. Freeman and Co., San Francisco, 1979). · Zbl 0411.68039
[13] S.L. Hakimi, ”Steiner problem in graphs and its implications,”Networks 2 (1971) 113–133. · Zbl 0229.05124 · doi:10.1002/net.3230010203
[14] F.K. Hwang, ”On Steiner minimal trees with rectilinear distance,”SIAM J. Appl. Math. 30(1) (1976) 106–114. · Zbl 0322.05101 · doi:10.1137/0130013
[15] E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[16] W. Liu, ”Extended formulations and polyhedral projection,” Ph.D. Dissertation, Department of Combinatorics and Optimization, University of Waterloo (1988).
[17] A. Prodon, T.M. Liebling and H. Groflin, ”Steiner’s problem on two-trees,” preprint (1985).
[18] J.A. Wald and C.J. Colbourn, ”Steiner trees, partial 2-trees and minimum IFI Networks,”Networks 13 (1983) 159–167. · Zbl 0529.68036 · doi:10.1002/net.3230130202
[19] K. White, M. Farber and W. Pulleyblank, ”Steiner trees, connected domination and strongly chordal graphs,”Networks 15 (1985) 109–124. · Zbl 0579.05050 · doi:10.1002/net.3230150109
[20] P. Winter, ”Steiner problem in network: A survey,”Networks 17 (1987) 129–167. · Zbl 0646.90028 · doi:10.1002/net.3230170203
[21] R.T. Wong, ”A dual ascent approach for Steiner tree problems on a directed graph,”Mathematical Programming 28 (1984) 271–287. · Zbl 0532.90092 · doi:10.1007/BF02612335
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.