Minimum Concave Cost Flow Over a Grid Network
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.
Entry Submitted: 10/12/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|