The minimum-concave-cost flow problem (MCNFP) is a constrained global optimization problem in which the solution space consists of valid flows in a given network. Flow through each arc incurs a non-negative, non-decreasing concave cost. There is a wide range of applications for the MCNFP including management of production systems, transportation and routing. Here we are concerned with the single source uncapacitated (SSU) version of the MCNFP. It requires establishing a minimum cost flow, from a single source to a set of sinks, through the network. This problem is known to be NP-hard which motivates the use of heuristic approaches. GRASP is a heuristic which has a strong intuitive appeal, a prominent empirical track record in combinatorial applications, and is trivial to efficiently implement on parallel processors. We develop comprising such a GRASP approach for the SSU MCNFP and provide computational results. We discuss a parallel implementation of a GRASP for the SSU MCNFP and provide computational results.

This is joint work with Kristina Holmqvist and Panos M. Pardalos.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing