Minimum concave cost flow over a grid network

• 成果类型: Article; Proceedings Paper
• 署名作者: He, Qie; Ahmed, Shabbir; Nemhauser, George L.
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0752-6
• 发表日期: 2015
• 页码: 79-98
• 关键词: inventory bounds; lot; algorithm; models

摘要

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.