HLPL / VerTeX Modelling Language Documentation

← formulations

# Aggregated (big-M) linking constraint
#
# Links assignments to open facilities with one aggregated row per facility.
# Fewer constraints than the disaggregated form, and the same integer
# optimum, but a materially weaker bound — which is what a branch-and-bound
# search actually searches against.
#
# Technique: One row per facility: sum_i x_ij <= |C|·y_j. Compact, but the
#            LP relaxation is weak because a single fractional y_j releases
#            every assignment at once.
#
# On this instance the optimum is 28 (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, 4}
const f = {11, 9}, forall j in F
const c = {{8, 5},
           {9, 4},
           {4, 2},
           {2, 8}}, 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
# aggregated: one row per facility, big-M = number of customers
constr sum_{i in C}{x_{i,j}} <= 4 * y_{j}, forall j in F
end

import elytica

Read this through MCP: read with path: "formulations/linking-aggregated", or resource hlpl://formulations/linking-aggregated.