# p-median facility location
#
# Places a fixed number of facilities to minimise average travel. Differs
# from uncapacitated location in that the count is a hard constraint rather
# than a cost, so there is no fixed charge to trade against.
#
# Technique: Open exactly p facilities and assign each demand point to an
# open one, minimising total weighted distance.
#
# On this instance the optimum is 7 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: 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
model m
set S = {1, 2, 3, 4}
set C = {1, 2, 3}
const d = {{12, 12, 4, 10},
{2, 8, 4, 2},
{3, 8, 1, 11}}, forall i in C, forall j in S
const p = 3
bin y, forall j in S
bin x, forall i in C, forall j in S
min sum_{i in C}{sum_{j in S}{d_{i,j} * x_{i,j}}}
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
# exactly p facilities, no more and no fewer
constr sum_{j in S}{y_{j}} = p
end
import elytica
Read this through MCP: read with path: "formulations/p-median", or resource hlpl://formulations/p-median.