Minimum concave cost flows in capacitated grid networks

We study the minimum concave cost flow problem over a two-dimensional grid network (CFG), where one dimension represents time ($1\le t\le T$) and the other dimension represents echelons ($1\le l\le L$). The concave function over each arc is given by a value oracle. We give a polynomial-time algorithm for finding the optimal solution when the network has a fixed number of echelons and all sources lie at one echelon. We also give an $O(T^4)$-time algorithm for finding the optimal solution in a capacitated grid network with two echelons and constant capacity on certain arcs. Both algorithms generalize the complexity results for many variants of the lot-sizing problem in terms of cost functions, number of echelons, intermediate demands, backlogging, and production and inventory capacities. We also show that CFG is NP-hard when the number of echelons is an input parameter or upward arcs are present. Our results resolve many of the complexity issues for CFG.

Article

Download

View Minimum concave cost flows in capacitated grid networks