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.

• 저널Management Science · 21(1) · 87–97
• 토픽Advanced Research in Systems and Signal Processing · Control and Systems Engineering
• DOI10.1287/mnsc.21.1.87
• 저자Andrés Weintraub