# Linear assignment
#
# Matches agents to tasks at least total cost. The constraint matrix is
# totally unimodular, so the LP relaxation is already integral and the
# binaries are a modelling convenience rather than a necessity.
#
# Technique: A doubly-stochastic 0/1 matrix: one row sum and one column sum
# equal to 1.
#
# On this instance the optimum is 15 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Kuhn, H. W. (1955). The Hungarian method for the assignment
# problem. Naval Research Logistics Quarterly 2(1–2), 83–97.
# doi:10.1002/nav.3800020109
model m
set I = {1, 2, 3, 4, 5}
set J = {1, 2, 3, 4, 5}
const c = {{9, 8, 13, 8, 5},
{2, 14, 2, 7, 1},
{13, 6, 13, 1, 3},
{15, 11, 4, 9, 2},
{11, 15, 2, 10, 15}}, forall i in I, forall j in J
bin x, forall i in I, forall j in J
min sum_{i in I}{sum_{j in J}{c_{i,j} * x_{i,j}}}
constr sum_{j in J}{x_{i,j}} = 1, forall i in I
constr sum_{i in I}{x_{i,j}} = 1, forall j in J
end
import elytica
Read this through MCP: read with path: "formulations/assignment", or resource hlpl://formulations/assignment.