IJPAM: Volume 49, No. 4 (2008)
COST NETWORK FLOW PROBLEMS
LIAAD-INESC Porto L.A.
Faculdade de Economia
Universidade do Porto
Rua Dr. Roberto Frias, Porto, 4200-464, PORTUGAL
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