Linear Approximations in a Dynamic Programming Approach for the Uncapacitated Single-Source Minimum Concave Cost Network Flow Problem in Acyclic Networks

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 so...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2001-02, Vol.19 (2), p.121
Main Authors: Burkard, Rainer E, Dollani, Helidon, Phan Thien Thach
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Costs
Dynamic programming
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-5001
1573-2916
DOI:10.1023/A:1008379621400