Accession Number:

ADA067756

Title:

A New Optimization Method for Large-Scale Fixed Charge Transportation Problems,

Descriptive Note:

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s):

• Barr,Richard S.
• Glover,Fred W.
• Klingman,Darwin D.

Report Date:

1979-03-01

Pagination or Media Count:

44.0

Abstract:

This paper presents a branch-and-bound algorithm for solving fixed charge transportation problems where not all cells exist. The algorithm exploits the absence of full problem density in several ways, thus yielding a procedure which is especially applicable to solving real-world problems which are normally quite sparse. Additionally, streamlined new procedures for pruning the decision tree and calculating penalties are presented. We present computational experience with both a set of large test problems and a set of dense test problems from the literature. Comparisons with other codes are uniformly favorable to the new method, which runs more than twice as fast as the best alternative. Author

Descriptors:

• *NETWORKS
• *LINEAR PROGRAMMING
• TRANSPORTATION
• OPTIMIZATION
• INTEGER PROGRAMMING
• SCHEDULING
• HEURISTIC METHODS
• MACHINE CODING

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE