Solving Concave Network Flow Problems

The Minimum Cost Network Flow Problem (MCNFP) includes a wide range of combinatorial optimization problems. Many applications exist for MCNFPs for instance supply chains, logistics, production planning, communications and transportations. Concave costs are, in many applications, more realistic than linear ones because of the association of prices with economies of scale. When concave costs are introduced in MCNFPs, then the difficulty to solve them increases and they become NP-Hard. Solution methods developed for these problems comprise both exact and approximate algorithms, the latter ones usually of a heuristic type. What we propose to do in this work is to present an overview of the past and most recent literature published on the subject.