  The p-median problem is a classic discrete location problem with several
applications. It aims to open p sites while minimizing the sum of the distances
of each client to its nearest open site. We study a Benders decomposition of
the most efficient formulation in the literature. We prove that the Benders
cuts can be separated by a polynomial time algorithm. The Benders decomposition
also leads to a new compact formulation for the p-median problem. We implement
a branch-and-Benders-cut approach that outperforms state-of-the-art methods on
benchmark instances by an order of magnitude.
