A Note on Garfinkel, Neebe and Rao's LP Decomposition for the p-Median Problem

The convergence problems of Garfinkel, Neebe and Rao's linear programming decomposition algorithm for the relaxed p-median problem are analyzed and traced back to the very degenerate nature of the LP formulation. Extensive computational experience with this algorithm is described. One surprising outcome of the tests conducted with the decomposition algorithm was that convergence was obtained more consistently when a random (and usually worse) initial solution was used instead of a “good” initial solution provided by heuristic methods.