A unified framework for primal-dual methods in minimum cost network flow problems. (English) Zbl 0567.90023
A broad class of algorithms for finding a minimum cost flow in a capacitated network is presented. The algorithms are of the primal-dual type and consist of a sequence, in any order, of three basic and flexible steps. Various alternatives for implementing these steps are described. Computational results with the new algorithms are presented in detail. These results indicate advantages in terms of computation time over classical methods.
Reviewer: E.Ciurea
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
| 05C35 | Extremal problems in graph theory |
Software:
NETGENReferences:
| [1] | H.A. Aashtiani and T.L. Magnanti, ”Implementing primal-dual network flow algorithms”, Operations Research Center Report 055-76, Massachusetts Institute of Technology, June 1976. |
| [2] | R.S. Barr, F. Glover and D. Klingman, ”The alternative basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1. · Zbl 0378.90097 · doi:10.1007/BF01584319 |
| [3] | D.P. Bertsekas, ”A new algorithm for the assignment problem”,Mathematical Programming 21 (1981) 153–171. · Zbl 0461.90069 · doi:10.1007/BF01584237 |
| [4] | D.P. Bertsekas and P. Tseng, ”Relaxation methods for minimum cost network flow problems” Laboratory for Information & Decision Systems Report LIDS-P-1339, Massachusetts Institute of Technology, October 1983. |
| [5] | G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, New Jersey, 1963). |
| [6] | L.R. Ford, Jr. and D.R. Fulkerson,Flows in networks (Princeton University Press, Princeton, New Jersey, 1962). · Zbl 0106.34802 |
| [7] | M.D. Grigoriadis, ”Algorithms for the minimum cost single and multi-commodity network flow problems”, Notes for Summer School in Combinatorial Optimization SOGESTA, Urbino, Italy, July 1978. |
| [8] | J. Kennington and R. Helgason,Algorithms for network programming, (Wiley, New York, 1980). · Zbl 0502.90056 |
| [9] | D. Klingman, A Napier, and J. Stutz, ”NETGEN–a program for generating large scale (un)capacitated assignment, transportation and minimum cost flow network problems”,Management Science 20 (1974) 814–822. · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814 |
| [10] | H.W. Kuhn, ”The Hungarian method for the assignment problem”,Naval Research Logistics Quarterly 2 (1955) 83–97. · Zbl 0143.41905 · doi:10.1002/nav.3800020109 |
| [11] | E.L. Lawler,Combinatorial optimization: Networks and matroids (Holt, Rinehart & Winston, New York, 1976). · Zbl 0413.90040 |
| [12] | L.F. McGinnis, ”Implementation and testing of a primal-dual algorithm for the assignment problem”,Operations Research 31 (1983) 277–291. · Zbl 0507.90055 · doi:10.1287/opre.31.2.277 |
| [13] | C.H. Papadimitriou and K. Steiglitz,Combinatorial optimization: Algorithms and complexity (Prentice Hall, Englewood Cliffs, New Jersey, 1982). · Zbl 0503.90060 |
| [14] | R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, New Jersey, 1970). · Zbl 0193.18401 |
| [15] | R.T. Rockafellar,Network flows and monotropic programming (Wiley, New York, 1984). · Zbl 0596.90055 |
| [16] | R.T. Rockafellar, ”Monotropic programming: Descent algorithms and duality”, O.L. Mangasarian, R. Meyer and S. Robinson, eds.,Nonlinear programming 4 (Academic Press, New York, 1981, 327–366). · Zbl 0537.49016 |
| [17] | T.E. Stern, ”A class of decentralized routing algorithms using relaxation”,IEEE Transactions on Communications COM-25 (1977) 1092–1102. · Zbl 0402.94047 |
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.
