p-Median Problem

PMP · HAKIMI 1964

Logistics · Network & Facility · Strategic

The p-Median Problem asks: given a set of demand nodes with known weights and a set of candidate facility sites, choose exactly $p$ facilities to open so that the total weighted distance from each demand node to its nearest open facility is minimised. Introduced by S. L. Hakimi (1964, 1965) who proved the seminal result that optimal medians can always be located on the vertices of the network, the p-Median is the cornerstone of location theory — the pure distance-minimisation formulation that every other location model extends or modifies.

Mathematical formulation

ReVelle-Swain (1970) IP · the canonical reference

SymbolMeaning
$I$candidate facility sites
$J$demand nodes
$w_j$demand weight at node $j$
$d_{ij}$distance from candidate $i$ to demand $j$
$p$required number of facilities to open (fixed)
$y_i \in \{0,1\}$1 if facility $i$ is opened
$x_{ij} \in \{0,1\}$1 if demand $j$ is assigned to facility $i$
Objective
$$\min \; \sum_{i \in I} \sum_{j \in J} w_j \, d_{ij} \, x_{ij}$$
(1) Each demand is assigned to exactly one facility
$$\sum_{i \in I} x_{ij} = 1 \quad \forall j \in J$$
(2) Assignment only to open facilities
$$x_{ij} \le y_i \quad \forall i \in I,\, j \in J$$
(3) Exactly $p$ facilities open
$$\sum_{i \in I} y_i = p$$
(4) Binary
$$y_i, x_{ij} \in \{0,1\}$$

Complexity. NP-hard for general $p \ge 2$ (Kariv & Hakimi 1979). In the LP relaxation, $x_{ij}$ can be relaxed to $[0,1]$ without changing the optimum when $d_{ij}$ satisfies the triangle inequality — so PMP is really a "0-1 $y$, continuous $x$" problem in practice.

Solution methods. Teitz-Bart (1968) vertex-interchange heuristic remains the go-to constructive method. Lagrangian relaxation on the assignment constraints (Cornuéjols, Fisher, Nemhauser 1977) gives strong lower bounds. Commercial MIP handles instances with $|I| \lesssim 1000$ routinely.

Key variants. p-Center replaces sum with max (minimax distance); uncapacitated facility location (UFLP) replaces cardinality $\sum y_i = p$ with fixed opening cost; capacitated p-median adds capacity at facilities.

Key references

Hakimi, S. L. (1964).
“Optimum locations of switching centers and the absolute centers and medians of a graph.”
Operations Research, 12(3), 450–459. doi:10.1287/opre.12.3.450
Hakimi, S. L. (1965).
“Optimum distribution of switching centers in a communication network and some related graph theoretic problems.”
Operations Research, 13(3), 462–475. doi:10.1287/opre.13.3.462
ReVelle, C. S., & Swain, R. W. (1970).
“Central facilities location.”
Geographical Analysis, 2(1), 30–42. doi:10.1111/j.1538-4632.1970.tb00142.x
Teitz, M. B., & Bart, P. (1968).
“Heuristic methods for estimating the generalized vertex median of a weighted graph.”
Operations Research, 16(5), 955–961. doi:10.1287/opre.16.5.955
Kariv, O., & Hakimi, S. L. (1979).
“An algorithmic approach to network location problems. II: The p-medians.”
SIAM Journal on Applied Mathematics, 37(3), 539–560. doi:10.1137/0137041
Cornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1977).
“Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms.”
Management Science, 23(8), 789–810. doi:10.1287/mnsc.23.8.789
Daskin, M. S. (2013).
Network and Discrete Location: Models, Algorithms, and Applications (2nd ed.).
Wiley. doi:10.1002/9781118537015

Siting facilities?
The cardinality constraint is the easy part — the distance weights do the work.

Get in Touch
Data and numerical examples are illustrative. Pages on this site are educational tools, not production software.