Abstract
In this paper 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.V. Aho, M.R. Garey and F.K. Hwang, “Rectilinear Steiner trees: Efficient special case algorithms,”Networks 7 (1977) 37–58.
Y.P. Aneja, “An integer linear programming approach to the Steiner problem in graphs,”Networks 10 (1980) 167–168.
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.
E. Balas and W. Pulleyblank, “The perfectly matchable subgraph polytope of a bipartite graph,”Networks 13 (1983) 495–516.
M. Ball, W. Liu and W. Pulleyblank, “Two-terminal Steiner tree polyhedra,” preprint (1988).
S. Chopra, “On the spanning tree polyhedron,”Operations Research Letters 8 (1989) 25–29.
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).
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.
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.
S.E. Dreyfus and R.A. Wagner, “The Steiner problem in graph,”Networks 1 (1972) 195–207.
D.R. Fulkerson, “Blocking and anti-blocking pairs of polyhedra,”Mathematical Programming 1 (1971) 168–194.
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).
S.L. Hakimi, “Steiner problem in graphs and its implications,”Networks 2 (1971) 113–133.
F.K. Hwang, “On Steiner minimal trees with rectilinear distance,”SIAM J. Appl. Math. 30(1) (1976) 106–114.
E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
W. Liu, “Extended formulations and polyhedral projection,” Ph.D. Dissertation, Department of Combinatorics and Optimization, University of Waterloo (1988).
A. Prodon, T.M. Liebling and H. Groflin, “Steiner's problem on two-trees,” preprint (1985).
J.A. Wald and C.J. Colbourn, “Steiner trees, partial 2-trees and minimum IFI Networks,”Networks 13 (1983) 159–167.
K. White, M. Farber and W. Pulleyblank, “Steiner trees, connected domination and strongly chordal graphs,”Networks 15 (1985) 109–124.
P. Winter, “Steiner problem in network: A survey,”Networks 17 (1987) 129–167.
R.T. Wong, “A dual ascent approach for Steiner tree problems on a directed graph,”Mathematical Programming 28 (1984) 271–287.
Author information
Authors and Affiliations
Additional information
Corresponding author.
Rights and permissions
About this article
Cite this article
Chopra, S., Rao, M.R. The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming 64, 209–229 (1994). https://doi.org/10.1007/BF01582573
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582573