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

摘要

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 method's 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. (Author)