Maximum network flows with concave gains

• 成果类型: Article
• 署名作者: Shigeno, M
• 署名单位: University of Tsukuba
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0608-1
• 发表日期: 2006
• 页码: 439-459
• 关键词: generalized circulation problem; algorithms; optimization

摘要

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs.