Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm

ABSTRACT

A computer code for the transportation problem that is even more efficient than the primal-dual method is developed. The code uses the well-known (primal) MODI method and is developed by a benefit-cost investigation of the possible strategies for finding an initial solution, choosing the pivot element, finding the stepping-stone tour, etc. A modified Row Minimum Start Rule, the Row Most Negative Rule for choice of pivot, and a modified form of the Predecessor Index Method for locating stepping-stone tours were found to perform best among the strategies examined. Efficient methods are devised for the relabeling that is involved in moving from one solution to another. The 1971 version of this transportation code solves both 100 × 100 assignment and transportation problems in about 1.9 seconds on the Univac 1108 Computer, which is approximately the same time as that required by the Hungarian method for 100 × 100 assignment problems. An investigation of the effect on mean solution time of the number of significant digits used for the parameters of the problem indicates that the cost parameters have a more significant effect than the rim parameters and that the solution time “saturates” as the number of significant digits is increased. The Minimum Cost Effect, i.e. the fact that total solution time asymptotically tends to the time for finding the initial solution as the problem size is increased (keeping the number of significant digits for the cost entries constant), is illustrated and explained. Detailed breakup of the solution times for both transportation and assignment problems of different sizes is provided. The paper concludes with a study of rectangular shaped problems.

REFERENCES

• 1: BALINSKI, M. L., AND GOMORY, R.E. A primal method for the assignment and transportation problem. Management Sci. 10 (1964), 578-593.
• 2: BARR, R. S., KLINGMAN, D., AND RAIKE, W.M. Computational simplifications through topological structure in network and distribution models. Ser. in Appl. Math. for Management, Publ. ~ AMM-13, Grad. Sch. Bus., U. of Texas, Austin, Texas, 1968.
• 3: CHARNES, A., AND COOPER, W.W. Management Models and Industrial Apphcations of Linear Programming, Vol. I. Wiley, New York, 1961.
• 4: DANTZm, G. B. Linear Programming and Extenszons. Princeton U. Press, Princeton, N.j., 1963.
• 5: Jack B. Dennis, A High-Speed Computer Technique for the Transportation Problem, Journal of the ACM (JACM), v.5 n.2, p.132-153, April 1958 [doi>10.1145/320924.320927]
• 6: FLORIAN, M., AND KLEIN, M. An experimental evaluation of some methods of solving the assignment problem. Canad. Oper. Res. 8oc. J. 8 (1970), 101-108.
• 7: FORD, L. R., AND FULKERSON, D.R. Flows in Networks. Princeton U. Press, Princeton, N. J., 1963.
• 8: GAVER, D. P., AND THOV{PSON, G. L. Programmzng and Probability Models in Operations Research. Brooks/Cole, Monterey, Calif., 1973.
• 9: GLICKSMAN, S., jOHNSON, L., AND ESELSON, L. Coding the transportation problems. Naval Res. Log. Quart. 7 (1970), 169-183.
• 10: GLOVER, F., KARNEY, D., KLINGMAN, D., AND NAPIER, A. A comparison of computation times for various starting procedures, basis change criteria, and solution algorithms for distribution problems. Res. Rep. CS ~44, Grad. Sch. Bus., U. of Texas, Austin, Texas, May 1971.
• 11: GLOVER, F., AND KLINGMAN, D. Locating stepping stone paths in distribution problems via the predecessor index method. Transportation Sci. ~ (1970), 220-225.
• 12: GLOVER, F., KLINGMAN, D., AND KARNEY, D. The augmented predecessor index method for locating stepping stone paths and assigning dual prices in distribution problems. Transportation Sci. (to appear).
• 13: HADLEY, G. Linear Programming Addison-Wesley, Reading, Mass., 1962.
• 14: JOHNSON, E. Networks and basic solutions. Oper. Res. 14 (1966), 619--623.
• 15: LEE, S. An experimental study of the transportation algorithms. Master's Th., Grad. Sch. Bus., U. of California, Los Angeles, Calif., 1968.
• 16: LOURIE, J. R. Topology and computation of the generalized transportation problem. Management 8ci. 11 (1964), 177-187.
• 17: MARCH, J. G., AND SIMON, H.A. Organizatzons. Wiley, New York, 1958.
• 18: ORCHARD-HAYS, W. Advanced Linear-Programming Computing Techniques. McGraw- Hill, New York, 1968.
• 19: P~EINFELD, N. V., AND VOGEL, W. R. Mathematical Programming. Prentice-Hall, Englewood Cliffs, N. J., 1958.
• 20: SPIVEY, W. A., AND THRALL, R.M. Linear Optimization. Holt, Rinehart and Winston, New York, 1970.
• 21: V. Srinivasan , G. L. Thompson, Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems, Journal of the ACM (JACM), v.19 n.4, p.712-726, Oct. 1972 [doi>10.1145/321724.321734]
• 22: R. Totschek , R. C. Wood, An Investigation of Real-Time Solution of the Transportation Problem, Journal of the ACM (JACM), v.8 n.2, p.230-239, April 1961 [doi>10.1145/321062.321070]
• 23: ZIMMER, R. P. Operational minimum path algorithms. Paper presented at 38th Nat. Conf. Oper. Res. Soc. of Amer., Detroit, 1970.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory