Abstract
The primary objectives of this paper are: (1) to present an improved formulation of the out-of-kilter algorithm; (2) to give the results of an extensive computational comparison of a code based on this formulation with three widely-used out-of-kilter production codes; (3) to study the possible sensitivity of these programs to the type of problem being solved; and (4) to investigate the effect of advanced dual start procedures on overall solution time.
The study discloses that the new formulation does indeed provide the most efficient solution procedure of those tested. This streamlined version of out-of-kilter was found to be faster than the other out-of-kilter codes tested (SHARE, BSRL and Texas Water Development Board codes) by a factor of 2–5 on small and medium size problems and by a factor of 4–15 on large problems. The streamlined method's median solution time for 1500 node networks on a CDC 6600 computer is 33 seconds with a range of 33 to 35 seconds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.L. Balinski and R.E. Gomory, “A primal method for the assignment and transportation problem”,Management Science 10 (1964) 578–593.
R.S. Barr, F. Glover and D. Klingman, “An imported version of the out-of-kilter method and a comparitive study of Computer Codes”, C.S. Rept. 102, Center for Cybernetic Studies, BEB 512, The University of Texas, Austin, Texas.
W.A. Briggs, “Algorithm 248 — Netflow (H)”,Communications of the Association for Computing Machinery 8 (2) (1965).
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, N.J., 1963).
J.B. Dennis, “A high-speed computer technique for the transportation problem”,Journal of the Association for Computing Machinery 8 (1958) 132–153.
D.W. Dijkstra, “A note on two problems in connexion with graphs”,Numerische Mathematik 1 (1959) 269–271.
M.M. Flood, “A transportation algorithm and code”,Naval Research Logistics Quarterly 8 (1961) 257–276.
L.R. Ford, Jr. and D. Fulkerson,Flows in networks (Princeton University Press, Princeton, N.J., 1962) p. 194.
L.R. Ford and D. Fulkerson, “A primal-dual algorithm for the capacitated Hitchcock problem”,Naval Research Logistics Quartely 4 (1) (1957) 47–54.
H. Frank and I.T. Frisch,Communication, transmission, and transportation networks (Addison-Wesley, Reading, Mass, 1971).
D.R. Fulkerson, “Flow networks and combinatorial operations research”,American Mathematical Monthly 73 (2) (1966) 115–138.
D.R. Fulkerson, “An out-of-kilter method for solving minimal cost flow problems”,Journal of the Society for Industrial and Applied Mathemetics 9 (1961) 18–27.
A.M. Geoffrion, Ed.,Perspectives on optimization: A collection of expository articles (Addison Wesley, Reading, Mass, 1972).
S. Glickman, L. Johnson and L. Eselson, “Coding the transportation problem”,Naval Research Logistics Quarterly 7 (1960) 169–183.
F. Glover, D. Karney, D. Klingman and A. Napier, “A computations study on start procedures, basis change criteria, and solution algorithms for transportation problems”,Management Science 20 (5) (1974) 793–813.
F. Glover and D. Klingman, “Double-pricing dual and feasible start algorithms for the capacitated transportation (distribution) problem”, University of Texas, Austin, Texas (1970).
F. Glover, D. Karney and D. Klingman, “The augmented predecessor index method for locating stepping stone paths and assigning dual prices in distribution problems”,Transportation Science 6 (1) (1972) 171–180.
M. Grigoriadis and W. Walker, “A treatment of transportation problems by primal partition programming”,Management Science 14 (9) (1968) 565–599.
M. Klein “A primal method for minimal cost flows with applications to assignment and transportation problems”,Management Science 14 (3) (1967) 205–220.
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 (5) (1974) 814–821.
S. Lee, “An experimental study of the transportation algorithms”, Master's Thesis, Graduate School of Business, University of California, Los Angeles, Calif. (1968).
M.-H. Mueller, “An improved starting algorithm for the Ford—Fulkerson approach to the transportation problem”,Management Science 13 (1) (1966) 97–104.
A. Napier, “A computer generator for uncapacitated networks”, unpublished.
“OPHELIE II: Mathematical programming system”, Control Data Corporation Minneapolis, Minn. (1970).
“OPHELIE/LP: Linear programming subsystem of OPHELIE II”, Control Data Corporation, Minneapolis, Minn. (1970).
“Out-of-kilter network routine”, SHARE Distribution 3536, SHARE Distribution Agency, Hawthorne, New York (1967).
J.-M. Pla, “An out-of-kilter algorithm for solving minimum cost potential problems”,Mathematical Programming 1 (1971) 275–290.
W.L. Price,Graphs and networks: An introduction (Auerbach, Princeton, N.J., 1971).
M. Simonnard,Linear programming (Prentice-Hall, Englewood Cliffs, N.J., 1966).
W.A. Spivey and R.M. Thrall,Linear optimization (Holt, Rinehart and Winston, New York, 1970).
V. Srinivasan and G.L. Thompson, “Benefit-cost analysis of coding techniques for the primal transportation algorithm”,Journal of the Association for Computing Machinery 20 (1973) 199–213.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barr, R.S., Glover, F. & Klingman, D. An improved version of the out-of-kilter method and a comparative study of computer codes. Mathematical Programming 7, 60–86 (1974). https://doi.org/10.1007/BF01585504
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585504