# Maximal covering location
#
# Places a limited number of facilities to cover as much demand as possible
# within a service radius, rather than to minimise distance. Coverage is an
# indicator dominated by the open facilities that can reach the point, which
# is the covering counterpart of p-median.
#
# Technique: A demand point counts as covered when at least one facility
# within range is open: z_i ≤ sum of y_j over the covering set.
#
# On this instance the optimum is 14 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Church, R. and ReVelle, C. (1974). The maximal covering
# location problem. Papers of the Regional Science Association 32(1),
# 101–118. doi:10.1007/BF01942293
model m
set S = {1, 2, 3, 4, 5}
set C = {1, 2, 3, 4, 5, 6}
set cov(C) = coveringFacilities()
const w = {3, 1, 5, 2, 1, 2}, forall i in C
const p = 3
bin y, forall j in S
bin z, forall i in C
max sum_{i in C}{w_{i} * z_{i}}
# a point counts as covered only if some facility in range is open
constr z_{i} <= sum_{j in cov(i)}{y_{j}}, forall i in C
constr sum_{j in S}{y_{j}} <= p
end
import elytica
def coveringFacilities():
return {1: [5], 2: [2, 4], 3: [4, 5], 4: [1, 4], 5: [2, 3, 4], 6: [1, 2]}
Read this through MCP: read with path: "formulations/max-covering", or resource hlpl://formulations/max-covering.