Accession Number : AD0749717

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

Descriptive Note : Research rept.,

Corporate Author : TEXAS UNIV AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s) : Glover,Fred ; Karney,D. ; Klingman,D. ; Napier,A.

Report Date : SEP 1972

Pagination or Media Count : 42

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)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), TRANSPORTATION, MATHEMATICAL MODELS, SIMPLEX METHOD, PROBABILITY, COMPUTER PROGRAMMING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE