A Computation Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation Problems

Fred Glover, D. Karney, D. Klingman and A. Napier
Additional contact information
Fred Glover: Professor of Management Science, University of Colorado, Boulder
D. Karney: Computer Analyst, Bureau of Business Research, University of Texas at Austin
D. Klingman: Associate Professor, Operations Research and Computer Science, U. of T. at Austin
A. Napier: Research Associate, Operations Research Division, Continental Oil Co., Houston, Texas

Management Science, 1974, vol. 20, issue 5, 793-813

Abstract: This paper presents an in-depth computational comparison of the basic solution algorithms for solving transportation problems. The comparison is performed using "state of the art" computer codes for the dual simplex transportation method, the out-of-kilter method, and the primal simplex transportation method (often referred to as the Row-Column Sum Method or M O D I method). In addition, these codes are compared against a state of the art large scale LP code, O P H E L I E/LP. The study discloses that the most efficient solution procedure arises by coupling a primal transportation algorithm (embodying recently developed methods for accelerating the determination of basis trees and dual evaluators) with a version of the Row Minimum start rule and a "modified row first negative evaluator" rule. The resulting method has been found to be at least 100 times faster than OPHELIE, and 9 times faster than a streamlined version of the SHARE out-of-kilter code. The method's median solution time for solving 1000 \times 1000 transportation problems on a CDC 6600 computer is 17 seconds with a range of 14 to 22 seconds. Some of the unique characteristics of this study are (1) all of the fundamental solution techniques are tested on the same machine and the same problems, (2) a broad spectrum of problem sizes are examined, varying from 10 \times 10 to 1000 \times 1000; (3) a broad profile of nondense problems are examined ranging from 100 percent to 1 percent dense; and (4) additional tests using the best of the codes have been made on three other machines (IBM 360/65, UNIVAC 1108, and CDC 6400), providing surprising insights into conclusions based on comparing times on different machines and compilers.

Date: 1974
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.20.5.783 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:20:y:1974:i:5:p:793-813

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().