A dual ascent approach for Steiner tree problems on a directed graph.(English)Zbl 0532.90092
Summary: The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node set V. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG’s containing up to 60 nodes and 240 directed/120 undirected arcs.
The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization of both the Chu-Liu- Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.
The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization of both the Chu-Liu- Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90B05 | Inventory, storage, reservoirs |
| 65K05 | Numerical mathematical programming methods |
| 05C35 | Extremal problems in graph theory |
| 90C10 | Integer programming |
Keywords:
computational results;Steiner tree problem;directed graph;directed subtree;dual ascent procedure;lower bounds to the optimal solution value;heuristic procedure;directed spanning tree;uncapacitated plant locationCite
Full Text:DOI
References:
| [1] | Y.P. Aneja, ”An integer linear programming approach to the Steiner problem in graphs”,Networks 10 (1980) 167–178. ·Zbl 0445.90087 ·doi:10.1002/net.3230100207 |
| [2] | O. Bilde and J. Krarup, ”Sharp lower bounds and efficient algorithms for the simple plant location problem”,Annals of Discrete Mathematics 1 (1977) 79–97. ·Zbl 0364.90068 ·doi:10.1016/S0167-5060(08)70728-3 |
| [3] | Y.J. Chu and T.H. Liu, ”On the shortest arborescences of a directed graph”,Scientia Sinica 14 (1965) 1396–1400. ·Zbl 0178.27401 |
| [4] | G. Cornuejols, M.L. Fisher and G.L. Nemhauser, ”Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms”,Management Science 23 (1977) 789–810. ·Zbl 0361.90034 ·doi:10.1287/mnsc.23.8.789 |
| [5] | S.E. Dreyfus and R.A. Wagner, ”The Steiner problem in graphs”,Networks 1 (1972) 195–207. ·Zbl 0229.05125 ·doi:10.1002/net.3230010302 |
| [6] | J. Edmonds, ”Optimum branchings”,Journal of Research of the National Bureau of Standards–B. Mathematics and Mathematical Physics 71B (1967) 233–240. ·Zbl 0155.51204 |
| [7] | R.E. Erickson, C.L. Monma and A.F. Veinott, Jr., ”Minimum concave cost network flows”, unpublished manuscript, Bell Laboratories (Holmdel, NJ, 1981). |
| [8] | D. Erlenkotter, ”A dual-based procedure for uncapacitated facility location”,Operations Research 26 (1978) 992–1009. ·Zbl 0422.90053 ·doi:10.1287/opre.26.6.992 |
| [9] | M.L. Fisher and D.S. Hochbaum, ”Database location in computer networks”,Journal of the ACM 27 (1980) 718–735. ·Zbl 0445.68071 ·doi:10.1145/322217.322226 |
| [10] | M.L. Fisher, R. Jaikumar and L. Van Wassenhov, ”A multiplier adjustment method for the generalized assignment problem”, contributed paper, ORSA/TIMS Meeting, Washington, D.C., May 1980. |
| [11] | M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness (W.H. Freeman and Co., San Francisco 1979). ·Zbl 0411.68039 |
| [12] | M. Guignard and K. Spielberg, ”A direct dual method for the mixed plant location problem with some side constraints”,Mathematical Programming 17 (1979) 198–228. ·Zbl 0416.90052 ·doi:10.1007/BF01588244 |
| [13] | M. Guignard and K. Spielberg, ”A direct dual approach to a transshipment formulation for multi-layer network problems with fixed charges”, Technical Report 43, Department of Statistics, University of Pennsylvania, (Philadelphia, PA, 1979). ·Zbl 0416.90052 |
| [14] | S.L. Hakirni, ”Steiner’s problem in graphs and its implications”,Networks 1 (1971) 113–133. ·Zbl 0229.05124 ·doi:10.1002/net.3230010203 |
| [15] | E. Lawler,Combinatorial optimization: Networks and matroids (Holt, Reinhart and Winston, New York, 1976). ·Zbl 0413.90040 |
| [16] | T.L. Magnanti and R.T. Wong, ”Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria”,Operations Research 29 (1981) 464–484. ·Zbl 0455.90064 ·doi:10.1287/opre.29.3.464 |
| [17] | T.L. Magnanti and R.T. Wong, ”Network design and transportation planning: Models and algorithms”,Transportation Science, to appear. |
| [18] | P.B. Mirchandani, ”Analysis of stochastic networks in emergency service systems”, Technical Report TR-15-75, Innovative Resources Planning Project, massachusetts Institute of Technology (Cambridge, MA, 1975). |
| [19] | R.L. Rardin, ”Tight relaxations of fixed charge network flow problems”, Technical Report J-82-3, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, GA, 1982). |
| [20] | R.L. Rardin, R.G. Parker and W.K. Lim, ”Some polynomially solvable multi-commodity fixed charge network flow problems”, Technical Report J-82-2, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, GA, 1982). |
| [21] | J. Suurballe, ”Algorithms for minimal trees and semi-Steiner trees based on the simplex method”, in: H.W. Kuhn, ed. Proceedings of the Princeton symposium on mathematical programming (Princeton University Press, Princeton, NJ, 1970) pp. 614–615. |
| [22] | R.E. Tarjan, ”Finding optimum branchings”,Networks 7 (1977) 25–35. ·Zbl 0379.90100 ·doi:10.1002/net.3230070103 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
