Optimization Online


Minimum Concave Cost Flow Over a Grid Network

Qie He(qie.he***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
George Nemhauser(george.nemhauser***at***isye.gatech.edu)

Abstract: The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple echelons. The polynomiality argument relies on a combination of a particular dynamic programming formulation and an investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow into any node in an extreme point solution, which generalizes a result of Zangwill (1968) for the multi-echelon lot-sizing problem.

Keywords: Min concave cost flow, Grid network, Lot-sizing model

Category 1: Network Optimization

Category 2: Combinatorial Optimization

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

Citation: Submitted for publication, 2012.

Download: [PDF]

Entry Submitted: 10/12/2012
Entry Accepted: 10/12/2012
Entry Last Modified: 10/12/2012

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