# 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.