optimization - Hungarian Algorithm not giving right result for multiple assignments -

the problem scenario :

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

• i need assign multiple tasks single worker.

  here cost matrix

  • i have 6 tasks , 3 workers available.

  • c (i,j) = 1, cell indicates, worker can assigned task.

  • c (i,j) = 1000, cell indicates, worker can not assigned 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 tasks ( task-1, task-4) worker2 can tasks ( task-2, task-5) worker3 can tasks ( task-6)

to create square matrix, added dummy workers : dworker1, dworker2 , dworker3) follows , assigned large value(1000000) 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 scipy package scipy.optimize.linear_sum_assignment. 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 col_ind array([5, 3, 4, 0, 1, 2])

the output indicates (if not wrong):

    - assign 6th task worker 1     - assign 4th task worker 2     - assign 5th task worker 3     - assign 1st task dummy worker 1     - assign 2nd task dummy worker 2     - assign 3rd task dummy worker 3 

what expecting is, assigning task ( 1, 2 , 3) real workers not dummy workers. possible through implementation? or missing here?

hungarian algorithm solving assignment problem, there 1 task assigned each worker. doing trick propose, indeed have 1 task assign each dummy worker also.

if interested in assigning tasks real workers, , assigning multiple tasks, easier : each task, select worker smallest cost. in example, means worker 1 tasks 1 , 4, worker 2 task 2 , 5, worker 3 task 6, , task 3 done 1 of 3 workers (depending on how handle equality case).