A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems

• Type: Article in International Scientific Journal
• Date: 2006

Authors

Dalila B.M.M. Fontes (Author) FEP; Eleni Hadjiconstatinou (Author) Other; Nicos Christofides (Author) Other

Journal

Title: European Journal of Operational Research

Vol. 174 No. 2

Pages: 1205-1219

ISSN: 0377-2217

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 24 Citations

ISI Web of Science

Scopus - 28 Citations

Scientific classification

FOS: Social sciences > Economics and Business

Other information

Authenticus ID: P-004-GJT

DOI: 10.1016/j.ejor.2005.03.024

Abstract (EN): In this paper, we describe a dynamic programming approach to solve optimally the single-source uncapacitated minimum cost network flow problem with general concave costs. This class of problems is known to be NP-Hard and there is a scarcity of methods to solve them in their full generality. The algorithms previously developed critically depend on the type of cost functions considered and on the number of nonlinear arc costs. Here, a new dynamic programming approach that does not depend on any of these factors is proposed. Computational experiments were performed using randomly generated problems. The computational results reported for small and medium size problems indicate the effectiveness of the proposed approach.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15