When I tried using scipy.optimize.linear_sum_assignment
as shown, it gives the assignment vector [0 2 3 1]
with a total cost of 15.
However, from the cost matrix c
, you can see that for the second task, the 5th agent has a cost of 1
. So the expected assignment should be [0 3 None 2 1]
(total cost of 9)
Why is linear_sum_assignment
not returning the optimal assignments?
from scipy.optimize import linear_sum_assignment
c = [
[1, 5, 9, 5],
[5, 8, 3, 2],
[3, 2, 6, 8],
[7, 3, 5, 4],
[2, 1, 9, 9],
]
results = linear_sum_assignment(c)
print(results[1]) # [0 2 3 1]
linear_sum_assignment
returns a tuple of two arrays. These are the row indices and column indices of the assigned values. For your example (withc
converted to a numpy array):The corresponding index pairs from
row
andcol
give the selected entries. That is, the indices of the selected entries are (0, 0), (1, 2), (3, 3) and (4, 1). It is these pairs that are the "assignments".The sum associated with this assignment is 9:
In the original version of the question (but since edited), it looks like you wanted to know the row index for each column, so you expected [0, 4, 1, 3]. The values that you want are in
row
, but the order is not what you expect, because the indices incol
are not simply [0, 1, 2, 3]. To get the result in the form that you expected, you have to reorder the values inrow
based on the order of the indices incol
. Here are two ways to do that.First:
Second:
Note that the example in the
linear_sum_assignment
docstring is potentially misleading; because it displays onlycol_ind
in the python session, it gives the impression thatcol_ind
is "the answer". In general, however, the answer involves both of the returned arrays.