I am having difficulty using scipy.optimize.linear_sum_assignment
to evenly distribute tasks (costs) to workers, where each worker can be assigned multiple tasks. The cost matrix represents the workload of each task for each worker.
We want to minimize the total costs of all workers, while evenly distributing the costs of each worker.
In this example, we have 3 workers named a
, b
and c
. Each worker can be assigned a total of 4 tasks, so in the cost matrix we have the agents a_1
, a_2
and so forth.
linear_sum_assignment
does give us the assignment with the total costs minimized. To simply things, our example uses a cost matrix such that any assignment will give us the same total costs.
However, is the costs is not evenly distributed across the 3 workers. In our example, the costs for the 3 workers are 65
, 163
and 192
respectively.
Is it possible to minimize the costs as much as possible, while distributing the costs per worker more evenly across the 3 workers?
from scipy.optimize import linear_sum_assignment
import numpy as np
worker_capacities = [
"a_1", "a_2", "a_3", "a_4",
"b_1", "b_2", "b_3", "b_4",
"c_1", "c_2", "c_3", "c_4",
]
n_tasks = len(worker_capacities)
c = np.array([
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
[27, 42, 65, 33, 67, 45, 60, 76, 6, 6, 43, 26],
])
_, assignments = linear_sum_assignment(c)
print("Costs for worker a:", sum(c[i][j] for i, j in enumerate(assignments[0:4])))
print("Costs for worker b:", sum(c[i+4][j] for i, j in enumerate(assignments[4:8])))
print("Costs for worker c:", sum(c[i+8][j] for i, j in enumerate(assignments[8:12])))
gives the output
Costs for worker a: 65
Costs for worker b: 163
Costs for worker c: 192
The
linear_sum_assignment
method doesn't support constraints or a custom objective, so I don't think this is possible.However, you could formulate your problem as a mixed-integer linear programming problem (MILP) and solve it by means of PuLP1. In order to evenly distribute the total costs per worker, you could minimize the difference between the maximum and the minimum total costs per worker. Here's a possible formulation:
The code is straightforward:
This gives me
[1] To be exact, PuLP isn't a solver, it's just a modelling framework that can pass MILPs to MILP Solvers like CBC, SCIP, HiGHS etc.