An Efficient Minimal Cost Flow Algorithm

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.

• 저널Management Science · 19(9) · 1042–1051
• 토픽Advanced Optical Network Technologies · Electrical and Electronic Engineering
• DOI10.1287/mnsc.19.9.1042
• 저자G. Bennington