Optimization Online


Minimum concave cost flows in capacitated grid networks

Qie He (qhe***at***umn.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
George Nemhauser (george.nemhauser***at***isye.gatech.edu)
Shi Li (shili***at***ttic.edu)

Abstract: 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.

Keywords: min concave cost flow; grid network; lot-sizing problem

Category 1: Network Optimization

Category 2: Combinatorial Optimization

Category 3: Applications -- OR and Management Sciences (Production and Logistics )


Download: [PDF]

Entry Submitted: 11/17/2013
Entry Accepted: 12/01/2013
Entry Last Modified: 03/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society