Accession Number:

AD0750254

Title:

An Efficient Minimal Cost Flow Algorithm.

Descriptive Note:

Operations research rept.,

Corporate Author:

NORTH CAROLINA STATE UNIV RALEIGH DEPT OF INDUSTRIAL ENGINEERING

Personal Author(s):

• Bennington,Gerald E.

Report Date:

1972-06-07

Pagination or Media Count:

28.0

Abstract:

One of the methods of solving the minimal cost flow problem is to find cycles of negative length in a marginal cost network. These negative cycles indicate a change in the flows around the cycle, which will result in a reduction in the total cost. The proposed method finds negative cycles by attempting to find the shortest chains from a fixed node to all other nodes. Results of computational experiments comparing this algorithm with the out-of-kilter algorithm are presented. These results indicate that the proposed method of repetitively detecting negative cycles yields an efficient minimal cost flow algorithm. Author

Descriptors:

• (*LINEAR PROGRAMMING
• ALGORITHMS)
• COSTS
• NETWORKS
• CONVEX SETS
• MATHEMATICAL MODELS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE