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

View Minimum concave cost flows in capacitated grid networks