Unbalanced worker/machine assignment
<p>I have a problem of assigning 7 possible workers to 3 machines. There is a cost when a worker is assigned to a machine as well as when a worker is idle. It is required that all 3 machines are used. The cost matrices are</p>

<pre><code>        M1  M2  M3
    W1 [72, 74, 74]         [64,
    W2 [48, 50, 50]          44,
C = W3 [52, 52, 52]     I =  52,
    W4 [40, 20, 18]          10,
    W5 [46, 48, 48]          42,
    W6 [40, 26, 26]          18,
    W7 [40, 20, 18]          12]
</code></pre>

<p>With matrix C being the cost of each worker being assigned to each machine. Matrix I represents the cost of each worker to be idle.</p>

<p>I'm currently using <code>scipy.optimize.linear_sum_assignment</code> to determine the minimum cost with a cost matrix </p>

<pre><code>        M1  M2  M3 
    W1 [72, 74, 74,64,M,M,M,M,M,M]         
    W2 [48, 50, 50,M,44,M,M,M,M,M]         
C = W3 [52, 52, 52,M,M,52,M,M,M,M]     With M being very big.   
    W4 [40, 20, 18,M,M,M,10,M,M,M]         
    W5 [46, 48, 48,M,M,M,M,42,M,M]         
    W6 [40, 26, 26,M,M,M,M,M,18,M]         
    W7 [40, 20, 18,M,M,M,M,M,M,12]          
</code></pre>

<p>With the current cost matrix it sometimes happens that not all machines are assigned. To counter this I simply multiplied all the idle cost with 10 to ensure that the machines are selected first.</p>

<p>My python code however does not give me the optimal answer. Is there maybe a different function I could use that would solves this type of problems?</p>

<p>The code:</p>

<pre><code>from scipy.optimize import linear_sum_assignment
C = [[72, 74, 74, 640, M, M, M, M, M, M],
    [48, 50, 50, M, 440, M, M, M, M, M],
    [52, 52, 52, M, M, 520, M, M, M, M],
    [40, 20, 18, M, M, M, 100, M, M, M],
    [46, 48, 48, M, M, M, M, 420, M, M],
    [40, 26, 26, M, M, M, M, M, 180, M],
    [40, 20, 18, M, M, M, M, M , M, 120]]

row_ind, col_ind = linear_sum_assignment(C)
print(row_ind)
print(col_ind )
</code></pre>

<p>I need a way to solve the assignment while forcing all three the machines to be assigned a worker. My way of defining the cost matrix seems to do it but doesn't give the wanted answer (obtained using a Tabu search). I'm not sure how to force <code>scipy.optimize.linear_sum_assignment</code> to always assign the three machines.
Is this even possible to do in <code>scipy.optimize.linear_sum_assignment</code> or should I rather be for a different python package to use?  </p>

<p>Found what was wrong with it. I had to many dummy machines allowing workers to be assigned to them rather than to the machines. By changing the dimensions of the matrix to be square (7x7) and changing the cost matrix    </p>

<pre><code>        M1  M2  M3 
    W1 [72, 74, 74,64,64,64,64]         
    W2 [48, 50, 50,44,44,44,44]         
C = W3 [52, 52, 52,52,52,52,52]    
    W4 [40, 20, 18,10,10,10,10]         
    W5 [46, 48, 48,42,42,42,42]         
    W6 [40, 26, 26,18,18,18,18]         
    W7 [40, 20, 18,12,12,12,12]
</code></pre>

<p><code>scipy.optimize.linear_sum_assignment</code> now gives me the correct assignment.</p>

python matrix variable-assignment