A Computation Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation Problems.
Abstract
The 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 MODI method). In addition, these codes are compared against a state of the art large scale LP code, OPHELIE/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 6 times faster than a streamlined version of the SHARE out-of-kilter code. The method's median solution time for solving 1000 x 1000 transportation problems on a CDC 6600 computer is 17 seconds with a range of 14 to 22 seconds. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1972
- Accession Number
- AD0749717
Entities
People
- A. Napier
- D. Karney
- D. Klingman
- Fred W. Glover
Organizations
- University of Texas at Austin