# Capacitated facility location
#
# Opens facilities and assigns customers subject to each site's throughput
# limit. The capacity row folds the linking constraint into itself — an
# unopened facility has zero capacity, so assignments to it are already
# forbidden — but the disaggregated link is usually kept anyway because it
# strengthens the relaxation.
#
# Technique: Uncapacitated location plus a capacity row per facility: sum_i
# d_i x_{i,j} <= k_j y_j.
#
# On this instance the optimum is 26 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Balinski, M. L. (1965). Integer programming: methods, uses,
# computation. Management Science 12(3), 253–313. doi:10.1287/mnsc.12.3.253
model m
set F = {1, 2, 3}
set C = {1, 2, 3, 4}
const f = {7, 13, 11}, forall j in F
const c = {{2, 5, 4},
{5, 4, 3},
{2, 3, 3},
{9, 2, 1}}, forall i in C, forall j in F
const d = {4, 3, 4, 4}, forall i in C
const k = {9, 9, 10}, forall j in F
bin y, forall j in F
bin x, forall i in C, forall j in F
min sum_{i in C}{sum_{j in F}{c_{i,j} * x_{i,j}}} + sum_{j in F}{f_{j} * y_{j}}
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
constr x_{i,j} <= y_{j}, forall i in C, forall j in F
# throughput limit; an unopened facility has zero capacity
constr sum_{i in C}{d_{i} * x_{i,j}} <= k_{j} * y_{j}, forall j in F
end
import elytica
Read this through MCP: read with path: "formulations/capacitated-facility-location", or resource hlpl://formulations/capacitated-facility-location.