Minimum-concave-cost flows in series-parallel networks
Julie Ann Ward · 1995
This 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 $A(N + K),$ where A, N and K are respectively the numbers of arcs, nodes and commodities in the network, and appears to be the first to solve the problem in polynomial time. When applied to the dynamic economic-order-quantity problem, the algorithm matches the performance of that of Wagner and Whitin (1958). Moreover, our algorithm has broader applications, including the multi-division capacity expansion problem and the generalization of the dynamic economic-order-quantity problem to series-parallel production processes in which subassemblies are assembled into a finished product. 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 $T\sp{2K{+}2}.$ When $K = 1,$ this running time matches that of an algorithm of Florian and Klein (1971). When $T = K,$ our algorithm runs in exponential time, reflecting the fact that this instance is known to be NP-hard. Thus, the algorithm bridges the gap between a class of known polynomially solvable problems and a class of NP-hard problems.