IJPAM: Volume 49, No. 4 (2008)

ON MINIMUM CONCAVE
COST NETWORK FLOW PROBLEMS

Dalila B.M.M. Fontes
LIAAD-INESC Porto L.A.
Faculdade de Economia
Universidade do Porto
Rua Dr. Roberto Frias, Porto, 4200-464, PORTUGAL
e-mail: fontes@fep.up.pt


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

Received: August 14, 2008

AMS Subject Classification: 90C35, 90C27, 90C26

Key Words and Phrases: network flow problems, combinatorial optimization, concave costs

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 49
Issue: 4