On minimum concave cost network flow problems

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

Authors

Dalila B.M.M. Fontes (Author) FEP

Journal

Title: International Journal of Pure and Applied Mathematics

Vol. 49 No. 4

Pages: 517-524

ISSN: 1311-8080

Publisher: Academic Publications Ltd

Scientific classification

FOS: Social sciences > Economics and Business

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research ; Social sciences > Economics > Management studies > Industrial management ; Social sciences > Economics > Management studies > Transport management

Other information

Abstract (EN): Minimum concave Cost Network Flow Problems (MCNFPs) arise naturally in many practical applications such as communication, transportation, distribution, and manufacturing, due to economic considerations. In addition, it has been shown that every MCNFP with general nonlinear cost functions can be transformed into a concave MCNFP on an expanded network. It must also be noted, that multiple source and capacitated networks can be transformed into single source and uncapacitated networks. The main feature defining the complexity of MCNFPs is the type of cost function for each arc. Concave MCNFPs are known to be NP-hard even for the simplest version (i.e. fixed-charge single source and uncapacitated). The review presented in this work describes several approaches to the design of Single Source Uncapacitated (SSU) flow networks involving concave costs.

Language: English

Type (Professor's evaluation): Scientific