Abstract
We describe a relaxation algorithm [1,2] for solving the classical minimum cost network flow problem. Our implementation is compared with mature state-of-the-art primal simplex and primal-dual codes and is found to be several times faster on all types of randomly generated network flow problems. Furthermore, the speed-up factor increases with problem dimension. The codes, called RELAX-II and RELAXT-II, have a facility for efficient reoptimization and sensitivity analysis, and are in the public domain.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.P. Bertsekas, A unified framework for minimum cost network flow problems, LIDS Report LIDS-P-1245-A, M.I.T. (1982); also Math. Progr. 32(1985)125.
D.P. Bertsekas and P. Tseng, Relaxation methods for minimum cost — ordinary and generalized network flow problems, LIDS Report LIDS-P-1462, M.I.T. (1985); also Oper. Res. Journal, to appear.
L.R. Ford, Jr. and D.R. Fulkerson,Flows in Networks (Princeton University Press, New Jersey, 1962).
D.P. Bertsekas, A new algorithm for the assignment problem, Math. Progr. 21(1982)152.
H.A. Aashtiani and T.L. Magnanti, Implementing primal-dual network flow algorithms, Oper. Res. Center Report 055-76, M.I.T. (1976).
T. Magnanti, Optimization for sparse systems, in:Sparse Matrix Computations, ed. J.R. Bunch and D.J. Rose (Academic Press, New York, 1976) pp. 147–176.
M.D. Grigoriadis and T. Hsu, The Rutgers minimum cost network flow subroutines (RNET documentation), Dept. of Computer Science, Rutgers University (1980).
J. Kennington and R. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).
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.
D.P. Bertsekas, P. Hosein and P. Tseng, Relaxation methods for network flow problems with convex arc costs, SIAM J. Control and Optimization 25(1987).
P. Tseng, Relaxation methods for monotropic programs, Ph.D. Thesis, M.I.T. (1986).
P. Tseng and D.P. Bertsekas, Relaxation methods for linear programs, LIDS Report LIDS-P-1553, M.I.T. (1986); also Math. of Oper. Res. 12(1987).
P. Tseng and D.P. Bertsekas, Relaxation methods for problems with strictly convex separable costs and linear constraints, LIDS Report LIDS-P-1567, M.I.T. (1986); also Math. Progr. 38(1987).
D.P. Bertsekas, Distributed relaxation methods for linear network flow problems,Proc. 25th IEEE Conf. on Decision and Control, Athens, Greece (1986).
D.P. Bertsekas and D. El Baz, Distributed asynchronous relaxation methods for convex network flow problems, LIDS Report LIDS-P-1417, M.I.T. (1984); also SIAM J. Control and Optimization 25(1987)74.
D.P. Bertsekas and J. Eckstein, Distributed asynchronous relaxation methods for linear network flow problems,Proc. of IFAC '87, Munich, Germany (1987) (Pergamon Press, Oxford).
Author information
Authors and Affiliations
Additional information
This work has been supported by the National Science Foundation under Grant NSF-ECS-8217668.
Rights and permissions
About this article
Cite this article
Bertsekas, D.P., Tseng, P. The relax codes for linear minimum cost network flow problems. Ann Oper Res 13, 125–190 (1988). https://doi.org/10.1007/BF02288322
Issue Date:
DOI: https://doi.org/10.1007/BF02288322