321. p-Median

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

321.1. Formulation

Choose facilities from candidate set to minimize:

s.t.:

(Here is the demand weight of customer .)

321.2. 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.

321.3. Solution methods

NP-hard. Methods:

• Branch-and-bound on MIP
• LP relaxation — strong; relaxation often gives integer optima
• Lagrangian relaxation — dualize 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)

321.4. 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

321.5. 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

321.6. See also

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