A heuristic for large-scale p-median instances

Given a digraph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a simple heuristic for large scale instances, consisting of three steps. First a lagrangean relaxation is solved to provide a lower bound. Then a simple procedure is used to choose "promising variables", defining a core problem. Finally the core problem is solved to optimality by branch-and-bound to provide good quality upper bounds. Computational experience is reported for instances up to 5934 nodes, showing that the duality gap is never larger than 1%.