1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – WimC
    Jul 25 '14 at 20:37
  • $\begingroup$ 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... $\endgroup$
    – Yay295
    Jul 25 '14 at 21:08
  • $\begingroup$ I've gotten it working. Thank you for the tips @WimC. $\endgroup$
    – Yay295
    Jul 26 '14 at 0:06
1
$\begingroup$

Thanks to WimC's comment on my question, I have gotten my code working. While all implementations of the Hungarian Method I have seen only assign zeroes if they are unique in their row and column, assigning random zeroes from those remaining seems to help with the line-drawing step. Doing so before drawing the lines has allowed my program to find an answer to this problem (it chose the first solution I posted at the bottom of my question). My program has been quite happily running on randomly generated matrices for three hours now, so this seems like a valid tactic to add to the Hungarian Method.

$\endgroup$
0
$\begingroup$

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

I used this method http://www.thp.uni-koeln.de/~berg/GraphAlignment/R-docs/LinearAssignment.html from this package http://www.thp.uni-koeln.de/~berg/GraphAlignment/ to do the calculation

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
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Yay295
    Jul 25 '14 at 19:37
  • $\begingroup$ @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 $\endgroup$ Jul 25 '14 at 20:00
  • $\begingroup$ I've taken a look at their code and found that they unfortunately use the more general Simplex Method rather than the Hungarian Method. While I'm sure it works very well (they seem to have spent quite a bit of time perfecting it), it doesn't actually help me. $\endgroup$
    – Yay295
    Jul 26 '14 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.