# Minimising a maximum
#
# Balances load across machines by minimising the largest load. The maximum
# becomes a single auxiliary variable dominating every term; minimisation
# pushes it to exactly the maximum.
#
# Technique: Replace max_i e_i by t with t ≥ e_i for all i.
#
# On this instance the optimum is 8 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Dantzig, G. B. (1963). Linear Programming and Extensions.
# Princeton University Press. doi:10.1515/9781400884179
model m
set J = {1, 2, 3, 4}
set M = {1, 2}
const p = {4, 3, 2, 6}, forall j in J
bin x, forall j in J, forall m in M
int 0 <= t <= 100
min t
# every job on exactly one machine
constr sum_{m in M}{x_{j,m}} = 1, forall j in J
# t dominates each machine load, so minimising t minimises the maximum
constr sum_{j in J}{p_{j} * x_{j,m}} <= t, forall m in M
end
import elytica
Read this through MCP: read with path: "formulations/minimax", or resource hlpl://formulations/minimax.