Algorithms for the single-source uncapacitated minimum concave-cost network flow problem

We investigate algorithms, applications, and complexity issues for the single-source uncapacitated (SSU) version of the minimum concave-cost network flow problem (MCNFP). We present applications arising from production planning, and prove complexity results for both global and local search. We formally state the local search algorithm of Gallo and Sodini 5], and present alternative local search algorithms. Computational results are provided to compare the various local search algorithms proposed and the effects of initial solution techniques.