Minimum concave cost flow over a grid network

Qie He, Shabbir Ahmed, George L. Nemhauser

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 (Manag Sci 14(7):429–450, 1968) for the multi-echelon lot-sizing problem.

Original languageEnglish (US)
Pages (from-to)79-98
Number of pages20
JournalMathematical Programming
Issue number1
StatePublished - Apr 2015

Bibliographical note

Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.


  • Grid network
  • Lot-sizing model
  • Min concave cost flow


Dive into the research topics of 'Minimum concave cost flow over a grid network'. Together they form a unique fingerprint.

Cite this