This paper presents extensive computational experience with a special purpose primal simplex algorithm. The performance is compared to that of several “state of the art” out-of-kilter computer codes. The computational characteristics of several different primal feasible start procedures and pivot selection strategies are also examined.

The study discloses the advantages, in both computation time and memory requirements, of the primal approach over the out-of-kilter method. The test environment has the following distinguishing properties: (1) all of the codes are tested on the same machine and the same problems, (2) the test set includes capacitated and uncapacitated transhipment networks, transportation problems, and assignment problems, and (3) problem sizes ranging from 200 to 8,000 nodes with up to 35,000 arcs are examined.

References

1 Barr, R. S., F. Glover and D. Klingman, “An Improved Version of the Out-of-Kilter Method and a Comparative Study of Computer Codes,” to appear in Mathematical Programming.
Google Scholar
2 Bennington, G. E., “ An Efficient Minimal Cost Flow Algorithm,” O. R. Report 75, North Carolina State University, Raleigh, North Carolina, June 1972.
Google Scholar
3 Charnes, A. and W. W. Cooper, Management Models and Industrial Applications of Linear Programming, 2 Vols., John Wiley & Sons, Inc., New York, 1961.
Web of Science® Google Scholar
4 Clasen, R. J., “ The Numerical Solution of Network Problems Using the Out-of-Kilter Algorithm,” RAND Corporation Memoramdum RM-5456-PR, Santa Monica, California, March, 1968.
Google Scholar
5 Dantzig, F., Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
10.1515/9781400884179
Web of Science® Google Scholar
6 Dennis, J. B., “A High-Speed Computer Technique for the Transportation Problem,” Journal of Association for Computing Machinery, 8, 1958, pp. 132–153.
10.1145/320924.320927
Web of Science® Google Scholar
7 Flood, M. M., “A Transportation Algorithm and Code,” Naval Research Logistics Quaterly, 8, 1971, pp. 257–276.
10.1002/nav.3800080308
Google Scholar
8 Ford, L. R. and D. Fulkerson, Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962.
10.1515/9781400875184
Google Scholar
9 Fong, C. O. and M. R. Rao, “ Accelerated Labeling Algorithms for the Maximal Flow Problem with Applications to Transportation and Assignment Problems,” W. P. No. 7222, Graduate School of Management, University of Rochester, December 1972.
Google Scholar
10 Fulkerson, D. R., “An Out-of-Kilter Method for Solving Minimal Cost Flow Problems,” J. Soc. Indust. Appl. Math., 9, 1961, pp. 18–27.
10.1137/0109002
Web of Science® Google Scholar
11 Glover, F., D. Karney and D. Klingman, “The Augmented Predecessor Index Method for Locating Stepping Stone Paths and Assigning Dual Prices in Distribution Problems,” Transprotation Science, 6, 1, 1972, pp. 171–180.
Google Scholar
12 Glover, F., D. Karney, D. Klingman and A. Napier, “A Computational Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation Problems,” Management Science, 20, 5, 1974, pp. 793–813.
10.1287/mnsc.20.5.783
Web of Science® Google Scholar
13 Glover, F., D. Karney and D. Klingman, “ Double-Pricing Dual and Feasible Start Algorithms for the Capacitated Transportation (distribution) Problem,” University of Texas at Austin, 1970.
Google Scholar
14 Glover, F., D. Klingman and A. Napier, “An Efficient Dual Approach to Network Problems,” OPSEARCH, 9, 1, 1972, pp. 1–18.
Google Scholar
15 Glover, F., D. Klingman and A. Napier, “Basic Dual Feasible Solution for a Class of Capacitated Generalized Networks,” Operations Research, 20, 1, 1972, pp. 126–137.
10.1287/opre.20.1.126
Web of Science® Google Scholar
16 Glover, F., D. Klingman and J. Stutz, “ The Augmented Threaded Index Method,” Research Report CS 144, Center for Cybernetic Studies, University of Texas, Austin, 1973.
Google Scholar
17 Glover, F., D. Karney and D. Klingman, “ A Note on Computational Studies for Solving Transportation Problems,” Proc. of the ACM 1973 Conference, Atlanta.
Google Scholar
18 Johnson, E., “Networks and Basic Solutions,” Operations Research, 14, 4, 1966, pp. 619–623.
10.1287/opre.14.4.619
Web of Science® Google Scholar
19 Klingman, D., A. Napier and G. Ross, “ A Computational Study on the Effects of Problem Dimensions on Solution Time for Transportation Problems,” Research Report CS 135, Center for Cybernetic Studies, University of Texas, Austin, 1973.
Google Scholar
20 Klingman, D., 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, pp. 814–821.
10.1287/mnsc.20.5.814
Web of Science® Google Scholar
21 Langley, R. W., “ Continuous and Integer Generalized Flow Problems,” Ph.D. dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, June 1973.
Google Scholar
22 Lee, S., “ An Experimental Study of the Transportation Algorithms,” Master's Thesis, Graduate School of Business, University of California at Los Angeles, 1968.
Google Scholar
23 “ Network Flow Routine,” YIM/FOCUS Library Number H3 CODA NETFLOW; Control Data Corporation, Software Mfg. and Distribution, 215 Moffett Park Drive, Sunnyvale, California.
Google Scholar
24 Orden, A., “The Transhipment Problem,” Management Science, 2, 3, 1956, pp. 276–285.
10.1287/mnsc.2.3.276
Web of Science® Google Scholar
25 “ Out-of-Kilter Network Routine,” SHARE Distribution 3536, SHARE Distribution Agency, Hawthorne, New York, 1967.
Google Scholar
26 Reinfield, N. V. and W. R. Vogel, Mathematical Programming, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1958.
Google Scholar
27 Srinivasan, V. and G. L. Thompson, “Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm,” JACM, 20, 1973, pp. 194–213.
10.1145/321752.321754
Web of Science® Google Scholar
28 “ UKILT-1100 Programmer Reference Manual,” UNIVAC, Data Processing Division, Roseville, Minnesota.
Google Scholar
29 Wagner, H., Principles of Operations Research, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1969.
Google Scholar

Citing Literature

Volume4, Issue3

1974

Pages 191-212

Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems

Abstract

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems

Abstract

References

Citing Literature

References

Related

Information