Single-source uncapacitated minimum concave-cost network flow problems

The authors investigate the single-source uncapacitated (SSU) version of the minimum concave-cost network flow problem (MCNFP). Specifically, they investigate the complexity of this class of problem in terms of global and local search. Computational results are presented that demonstrate that various local search techniques are very efficient on randomly generated test networks. Results for various initial solution techniques indicate that the initial solution has little effect on the magnitude of the final solution, but has a significant effect on the rate of convergence.