A Dual-Bounded Algorithm for the p-Median Problem

The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is developed and tested in a branch-and-bound algorithm. Computational results show that the resulting solution procedure has some advantages over existing exact methods for this problem.