Minimum-concave-cost flows in series-parallel networks

his work develops polynomial-time dynamic-programming algorithms for two classes of minimum-concave-cost flow problems in series-parallel networks. Significant problems from production and inventory management, capacity planning, network design and transportation can be formulated in these terms.;A directed graph is series-parallel if it can be constructed from a single directed arc by a finite sequence of expansions each involving replacement of an arc either by arcs in series or by arcs in parallel. A graph is strong-series-parallel if it is series-parallel and the series and parallel replacements in its construction preserve the direction of the arcs they replace.;The first class of problems is the minimum-aggregate-concave-cost multicommodity uncapacitated flow problem in a strong-series-parallel network. In this problem, the cost of a flow is the sum of concave functions, each depending on the aggregate flow in an arc. Our results for this problem include a characterization of extreme flows in strong-series-parallel networks and an algorithm based on this characterization that searches extreme flows efficiently to find an optimal one. The algorithm runs in time proportional to ;The second class of problems considered in this work is the minimum-concave-cost T-period capacitated dynamic economic-order-quantity problem in which there are at most K different capacities. This problem can be reduced to one of uncapacitated network flows. Although the resulting network is series-parallel, it is not strongly so. Thus the above algorithm does not apply. Our method generalizes the Wagner-Whitin algorithm for the uncapacitated problem to the capacitated case and runs in time proportional to...