# p-center (minimax location)
#
# Places p facilities so the furthest customer is as close as possible. The
# objective is minimax where p-median is min-sum, so the same data and the
# same assignment variables give a different answer — this is the
# equity-oriented counterpart, driven by the worst case rather than the
# average.
#
# Technique: Minimise the worst assignment distance with an auxiliary
# variable: t >= d_{i,j} x_{i,j} for every pair, then minimise
# t.
#
# On this instance the optimum is 5 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Kariv, O. and Hakimi, S. L. (1979). An algorithmic approach to
# network location problems. I: the p-centers. SIAM Journal on Applied
# Mathematics 37(3), 513–538.
model m
set S = {1, 2, 3, 4}
set C = {1, 2, 3, 4}
const d = {{9, 5, 7, 9},
{1, 2, 10, 1},
{6, 7, 10, 2},
{7, 8, 11, 4}}, forall i in C, forall j in S
const p = 2
bin y, forall j in S
bin x, forall i in C, forall j in S
int 0 <= t <= 11
min t
constr sum_{j in S}{x_{i,j}} = 1, forall i in C
constr x_{i,j} <= y_{j}, forall i in C, forall j in S
constr sum_{j in S}{y_{j}} = p
# t dominates every realised assignment distance, so minimising it
# minimises the worst one
constr t >= d_{i,j} * x_{i,j}, forall i in C, forall j in S
end
import elytica
Read this through MCP: read with path: "formulations/p-center", or resource hlpl://formulations/p-center.