Complementary Approaches for a Clustering Problem

The lagrangean/surrogate relaxation has been explored as a faster computational alternative to traditional lagrangean heuristics. This paper discusses two approaches for using lagrangean/surrogate heuristics to a classical clustering problem: the p-median problem, that is, how to locate p facilities (medians) on a network such as the sum of all the distances from each vertex to its nearest facility is minimized