A transportation algorithm and code

A FORTRAN II transportation code, using Kuhn's Hungarian Method, was reported upon at the RAND Symposium on Mathematical Programming in March 1959. The algorithm was based upon a proof of the König‐Egervary theorem, presented by the present author at the 1958 Symposium on Combinatorial Problems sponsored by the American Mathematical Society. The code was entirely rewritten (in FORTRAN II), during the 1959 IBM Summer Institute on Combinatorial Problems, and several problems were run at the IBM Research Center to obtain data regarding computing times and frequencies of various internal loops. A CLOCK Subroutine yields readings, in hundredths of minutes, for each time through selected portions of the computing run. The version reported upon at RAND solved a 29 × 116 pseudorandom transportation problem in 8.01 min, as compared with 3.17 min using the fastest competing code (SHARE 464) then available. The present version solved this same problem in 2.87 min, and another 29 × 116 problem in 1.89 min. This paper presents the algorithm and reports upon computing experience.