A PRIMAL ALGORITHM TO SOLVE NETWORK FLOW PROBLEMS WITH CONVEX COSTS.

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]