334. p-Median

$𝑝$-Median Problem: place exactly $𝑝$ facilities among candidates to minimize the total assigned distance / cost. No fixed facility cost — the constraint is “exactly $𝑝$”.

334.1. Formulation

Choose $𝑝$ facilities from candidate set $𝐽$ to minimize:

s.t.:

(Here ${𝑑}_{𝑖}$ is the demand weight of customer $𝑖$.)

334.2. Picture

Customer disc size $\propto$ demand weight ${𝑑}_{𝑖}$ — $𝑝=2$ facilities chosen to minimize total weighted distance.

334.3. Difference from UFLP

• UFLP: facility costs are variable — pay ${𝑓}_{𝑗}$ to open. Optimizer picks the right number.
• $𝑝$-Median: exactly $𝑝$ facilities — number is fixed by the problem. No per-facility fixed cost.

In practice, the two are related: solving $𝑝$-median for varying $𝑝$ traces out the cost-vs-number-of-facilities trade-off curve that UFLP would balance via the fixed costs.

334.4. Solution methods

NP-hard. Methods:

• Branch-and-bound on MIP
• LP relaxation — strong; relaxation often gives integer optima
• Lagrangian relaxation — dualize ${\sum }_{𝑗}{𝑦}_{𝑗}=𝑝$ to get $𝑝$-median dualizing the cardinality
• Greedy / interchange heuristics (Teitz-Bart, swap-based local search)
• Approximation: 3-approximation for metric $𝑝$-median (Lin-Vitter, Charikar-Guha)

334.5. Applications

• Distribution center placement — find best $𝑝$ of $𝑛$ candidates
• Service location — fire stations, branches
• Cell phone tower placement — when budget fixes count $𝑝$
• Vendor consolidation — pick $𝑝$ suppliers from larger pool

334.6. Variants

• Continuous $𝑝$-median (1-median = center of gravity multi-facility versions: Weiszfeld iteration generalized)
• $𝑝$-center ($𝑝$-center) — minimize max distance instead of total
• Capacitated $𝑝$-median — facilities have capacity limits
• Multi-objective — trade off coverage / equity / total cost

334.7. See also

• UFLP — variable count, fixed costs
• $𝑝$-center — minimax variant
• Center of Gravity — $𝑝=1$ continuous case
• Facility Location overview