3 ms·
Actually, you can solve the assignment problem as a linear program (LP). Just do min sum_i sum_j c_{ij}*x_{ij} s.t. sum_i x_{ij} == 1, for all j
by cschmidt 2y ago
Actually, you can solve the assignment problem as a linear program (LP). Just do
min sum_i sum_j c_{ij}*x_{ij}
s.t. sum_i x_{ij} == 1, for all j
sum_j x_{ij} == 1, for all i
and you automagically get an integer solution in the x_{ij} due to the structure of the constraints.
CVXPY would be a good way to implement this these days.