# Linear sum assignment, but with ranked assignments?

Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix:

cost_matrix = np.array([
[4, 2, 8, 7, 8],
[6, 4, 3, 2, 1],
[7, 5, 2, 1, 2],
[7, 9, 2, 8, 5],
[2, 2, 3, 7, 9]
])


Using scipy's optimization library, I can get assignments for each agent:

from scipy.optimize import linear_sum_assignment
row_ind, col_ind = linear_sum_assignment(cost_matrix)
for row, col in zip(row_ind, col_ind):
print(f"Task {row} is assigned to Agent {col}")


However, what if I'm only interested in the agents to assign task 0? Let's say I just want to understand for task 0 only a ranked list of agents to assign to that task, but still with the goal of minimizing total system-wide cost. Is there any way to solve for this problem?

• What about maybe solving the LAP n(umber agents) times, while each iteration fixes a different agent to task 0. Rank by objective-values after. I guess such partial-fixing should be trivial given a LP-based LAP-solver (a variable-bound of [1,1] instead of [0,1] doesn't destroy any relevant structure, e.g. total unimodularity). (One could even exploit warm-start / incrementality to speed it up i guess) Commented May 21 at 1:34
• @sascha Ended up going with this approach! Added benefit is that I was able to run iterations in parallel thereby reducing runtime.
– Dan
Commented May 31 at 17:21