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?

  • 2
    $\begingroup$ 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) $\endgroup$
    – sascha
    Commented May 21 at 1:34
  • 1
    $\begingroup$ @sascha Ended up going with this approach! Added benefit is that I was able to run iterations in parallel thereby reducing runtime. $\endgroup$
    – Dan
    Commented May 31 at 17:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.