  


Minimum concave cost flows in capacitated grid networks
Qie He (qheumn.edu) Abstract: We study the minimum concave cost flow problem over a twodimensional 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 polynomialtime 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 lotsizing problem in terms of cost functions, number of echelons, intermediate demands, backlogging, and production and inventory capacities. We also show that CFG is NPhard when the number of echelons is an input parameter or upward arcs are present. Our results resolve many of the complexity issues for CFG. Keywords: min concave cost flow; grid network; lotsizing problem Category 1: Network Optimization Category 2: Combinatorial Optimization Category 3: Applications  OR and Management Sciences (Production and Logistics ) Citation: Download: [PDF] Entry Submitted: 11/17/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  