# Disaggregated linking constraint
#
# Links each assignment to its facility individually. It describes exactly
# the same integer feasible set as the aggregated form and reaches the same
# optimum, but its relaxation is at least as strong and usually strictly
# stronger, which is the classic size-versus-strength trade-off.
#
# Technique: One row per assignment: x_ij <= y_j. More rows, but the LP
# relaxation is tight — this is the ideal formulation of the
# same set.
#
# On this instance the optimum is 16 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Vielma, J. P. (2015). Mixed integer linear programming
# formulation techniques. SIAM Review 57(1), 3–57. doi:10.1137/130915303
model m
set F = {1, 2}
set C = {1, 2, 3}
const f = {9, 4}, forall j in F
const c = {{8, 7},
{6, 4},
{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}}
constr sum_{j in F}{x_{i,j}} = 1, forall i in C
# disaggregated: one row per (customer, facility) pair
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/linking-disaggregated", or resource hlpl://formulations/linking-disaggregated.