A Suggested Computation for Maximal Multi-Commodity Network Flows

Abstract

(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.