Accession Number:

AD0730704

Title:

A Comparison of Computation Times for Various Starting Procedures, Basis Change Criteria, and Solution Algorithms for Distribution Problems

Descriptive Note:

Research rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Report Date:

1971-05-01

Pagination or Media Count:

32.0

Abstract:

New methods for accelerating the determination of basis trees and dual evaluators for distribution problems are compared with standard solution procedures in a computational study of a wide range of distribution problems of varying sizes and densities. Computer programs utilizing the new methods are tested for computational efficiency in an experiment involving four solution techniques, four start algorithms, and four change of basis criteria, thus affording an empirical determination not only of the merits of various procedures in isolation but also of their effectiveness in combination. The study discloses that the most efficient solution procedure arises by coupling a primal transportation algorithm embodying the accelerated updating and pricing methods with a version of the Row Minimum start rule and a modified first negative evaluator rule. The resulting method was found to improve upon the efficiency of general purpose algorithms taken from standard computer packages by a factor of 50 or better, and also improved upon a streamlined version of the SHARE out-of-kilter code by a factor of 3. The methods median solution time for solving 175 x 175 distribution problems on a CDC 6600 computer was 11.4 seconds with a range of 9 to 13 seconds.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE