Hungarian Algorithm not giving right result for multiple assignments

Question

The problem scenario :

• The number of tasks(n) is greater than the number of workers(m).

• I need to assign multiple tasks to a single worker.

  Here is the cost matrix

  • I have 6 tasks and 3 workers available.

  • C (i,j) = 1, for the cell which indicates, worker can be assigned to task.

  • C (i,j) = 1000, for the cell which indicates, worker can not be assigned to task.

The cost matrix

  TASK/WORKER        WORKER1   WORKER2  WORKER3

    TASK 1           1          1000     1000

    TASK 2           1000       1        1000

    TASK 3           1000       1000     1000

    TASK 4           1          1000     1000

    TASK 5           1000       1        1000

    TASK 6           1000       1000     1

Here , worker1 can do tasks ( TASK-1, TASK-4) worker2 can do tasks ( TASK-2, TASK-5) worker3 can do tasks ( TASK-6)

To create square matrix, I added dummy WORKERS : DWORKER1, DWORKER2 and DWORKER3) as follows and assigned very large value(1000000) to the cell value.

 TASK/WORKER        WORKER1   WORKER2  WORKER3  DWORKER1  DWORKER2 DWORKER3

    TASK 1           1          1000     1000   1000000   100000    1000000

    TASK 2           1000       1        1000   1000000   100000    1000000

    TASK 3           1000       1000     1000   1000000   100000    1000000

    TASK 4           1          1000     1000   1000000   100000    1000000

    TASK 5           1000       1        1000   1000000   100000    1000000

    TASK 6           1000       1000     1       1000000   100000    1000000

I used the scipy package scipy.optimize.linear_sum_assignment. As follows:

from scipy.optimize import linear_sum_assignment

cost = np.array([[1,1000,1000,1000000,100000,1000000],[1000,1,1000,1000000,1000000,1000000],[1000,1000,
1000,1000000,100000,1000000],[1,1000,1000,1000000,1000000,1000000],[1000,1,1000,1000000,100000,  1000000],[1000,1000,1,1000000,1000000,1000000]])

row_ind, col_ind = linear_sum_assignment(cost)

The output for col_ind is array([5, 3, 4, 0, 1, 2])

The output indicates (If I am not wrong):

    - Assign 6th task to worker 1
    - Assign 4th task to worker 2
    - Assign 5th task to worker 3
    - Assign 1st task to Dummy worker 1
    - Assign 2nd task to Dummy worker 2
    - Assign 3rd task to Dummy worker 3

What I am expecting is, assigning TASK ( 1, 2 and 3) to the real workers not the dummy workers. Is that possible through this implementation? Or I am missing anything here?

Answer 1

Hungarian algorithm is for solving the assignment problem, where there is exactly one task assigned to each worker. By doing the trick you propose, you will indeed have 1 task assign to each dummy worker also.

If you are interested in only assigning tasks to real workers, and assigning multiple tasks, that is much easier : for each task, select the worker with the smallest cost. In your example, it means that worker 1 will do tasks 1 and 4, worker 2 will do task 2 and 5, worker 3 will do task 6, and task 3 will be done by one of the three workers (depending on how you handle the equality case).