A Suggested Computation for Maximal Multi-Commodity Network Flows

(This article originally appeared in Management Science, October 1958, Volume 5, Number 1, pp. 97–101, published by The Institute of Management Sciences.) A simplex computation for an arc-chain formulation of the maximal multi-commodity network flow problem is proposed. Since the number of variables in this formulation is too large to be dealt with explicitly, the computation treats non-basic variables implicitly by replacing the usual method of determining a vector to enter the basis with several applications of a combinatorial algorithm for finding a shortest chain joining a pair of points in a network.

• 저널Management Science · 50(12_supplement) · 1778–1780
• 토픽Optimization and Mathematical Programming · Control and Systems Engineering
• DOI10.1287/mnsc.1040.0269
• 저자L. R. Ford, D. R. Fulkerson