# Unsolvable(?) Assignment Problem

I've recently been trying to implement the Hungarian Method in C++, and I've been using 5x5 matrices to test my program. Last night I came across a matrix which neither I nor my program can solve. Is it truly unsolvable, or am I missing something?
It starts like this:

\begin{bmatrix}2&3&7&4&8\\5&0&8&8&7\\1&5&0&5&3\\7&1&8&7&7\\4&9&3&8&6\end{bmatrix}

and after row and column reduction I get this:

\begin{bmatrix}0&1&5&0&3\\5&0&8&6&4\\1&5&0&3&0\\6&0&7&4&3\\1&6&0&3&0\end{bmatrix}

Assignments are made and lines are drawn:

\begin{bmatrix}A&1&5&0&3\\5&A&8&6&4\\1&5&0&3&0\\6&0&7&4&3\\1&6&0&3&0\end{bmatrix}\begin{bmatrix}-&+&+&-&-\\5&|&|&6&|\\1&|&|&3&|\\6&|&|&4&|\\1&|&|&3&|\end{bmatrix}

and I get this matrix:

\begin{bmatrix}0&2&6&0&4\\4&0&8&5&4\\0&5&0&2&0\\5&0&7&3&3\\0&6&0&2&0\end{bmatrix}

After another round of assigning and line-drawing I get this:

\begin{bmatrix}2&4&8&0&6\\4&0&8&3&4\\0&5&0&0&0\\5&0&7&1&3\\0&6&0&0&0\end{bmatrix}

and can't go any further. The only assignments that can be made are in the first two rows, and when the lines are drawn every column is covered. I had thought this meant that multiple solutions exist, but I can't find them.

edit: I have brute-forced this to find the correct answers. With (0,0) being the top left, and (4,4) being the bottom right, the solutions are as follows:
(0,0)(1,1)(2,2)(3,3)(4,4) = 2, 0, 0, 7, 6 = 15
(3,0)(1,1)(2,2)(4,3)(0,4) = 4, 0, 0, 7, 4 = 15

Brute force is not going to work on larger matrices though, so I need a better solution.

edit 2: I missed one. Credit to sanjab.
(0,0)(1,1)(4,2)(3,3)(2,4) = 2, 0, 3, 7, 3 = 15

• I'm not familiar with the algorithm but I have two observations: Firstly you can assign more than you indicate (it is not necessary that a zero is unique in a row or column to assign it). Secondly, you do not use the minimum number of lines to cover the zeros. For example the matrix obtained after the first round can be covered by four lines while it seems that you used five.
– WimC
Jul 25 '14 at 20:37
• In the Hungarian Algorithm, only unique zeroes are assigned because they are the only ones we know for sure are in the solution. The line-drawing is then done to modify the matrix in a way as to get more zeroes to assign. You're correct that I didn't use the minimum number of lines though, I hadn't noticed that. My program would have actually found a solution if four lines had been used. I can now see how to cover the zeroes with four lines, the problem is how to I get my program to do it... Jul 25 '14 at 21:08
• I've gotten it working. Thank you for the tips @WimC. Jul 26 '14 at 0:06

I don't know much about it. But I just calculated it with R. Using your matrix I get the result: $(5, 2, 3, 1, 4)$
R code I used:  library("GraphAlignment") m <- matrix(c(2,5,1,7,4,3,0,5,1,9,7,8,0,8,3,4,8,5,7,8,8,7,3,7,6),5) px <- LinearAssignment(m) px 
EDIT: This looks like it is wrong. I calculated it again with a different package:  library("lpSolve") assign.costs <- matrix(c(2,5,1,7,4,3,0,5,1,9,7,8,0,8,3,4,8,5,7,8,8,7,3,7,6),5) lp.assign (assign.costs) lp.assign (assign.costs)$solution  This outputs:  [,1] [,2] [,3] [,4] [,5] [1,] 1 0 0 0 0 [2,] 0 1 0 0 0 [3,] 0 0 0 0 1 [4,] 0 0 0 1 0 [5,] 0 0 1 0 0  • The sum of that does happen to be the minimum (15), but it is not a correct answer. The only 2 in the original matrix is in the top left corner. The only 4's are in the top row, and in the left row. Thus, a solution cannot have both a 2 and a 4. Jul 25 '14 at 19:37 • @Yay295 You are correct. I calculated it again with a different package, this looks like it gives a better solution: library("lpSolve") assign.costs <- matrix(c(2,5,1,7,4,3,0,5,1,9,7,8,0,8,3,4,8,5,7,8,8,7,3,7,6),5) lp.assign (assign.costs) lp.assign (assign.costs)$solution Jul 25 '14 at 20:00