# Uncapacitated facility location
#
# Opens facilities and assigns every customer to one, trading fixed opening
# cost against service cost. The disaggregated linking constraint is used
# rather than sum_i x_ij <= n·y_j, because the disaggregated form gives a
# substantially stronger LP relaxation.
#
# Technique: Variable upper bound x_{i,j} <= y_j links assignment to an
# open facility, which is tighter than aggregating into one
# big-M row.
#
# On this instance the optimum is 16 (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 = {6, 5, 9}, forall j in F
const c = {{7, 4, 1},
{4, 1, 4},
{5, 3, 4},
{6, 3, 1}}, forall i in C, 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}}
# each customer served exactly once
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
# and only by a facility that is open (disaggregated form)
constr x_{i,j} <= y_{j}, forall i in C, forall j in F
end
import elytica
Read this through MCP: read with path: "formulations/uncapacitated-facility-location", or resource hlpl://formulations/uncapacitated-facility-location.