Linear Approximations in a Dynamic Programming Approach for the Uncapacitated Single-Source Minimum Concave Cost Network Flow Problem in Acyclic Networks |
| |
Authors: | Rainer E Burkard Helidon Dollani Phan Thien Thach |
| |
Institution: | (1) Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria;(2) Institute of Mathematics, P.O. Box 631, Bo Ho, Hanoi, Vietnam |
| |
Abstract: | We consider minimum concave cost flow problems in acyclic, uncapacitated networks with a single source. For these problems a dynamic programming scheme is developed. It is shown that the concave cost functions on the arcs can be approximated by linear functions. Thus the considered problem can be solved by a series of linear programs. This approximation method, whose convergence is shown, works particularly well, if the nodes of the network have small degrees. Computational results on several classes of networks are reported. |
| |
Keywords: | Uncapacitated single-source acyclic networks Concave costs Dynamic programming Linear approximation Convergence |
本文献已被 SpringerLink 等数据库收录! |
|