Cannot solve Hungarian Algorithm

Question

I'm trying to implementing a function to solve the hungarian algorithm and i think that there is something i have misunderstood about the algorithm.

For testing purposes i'm using this c++ code from google that is supposed to work.

But when i test this 14x11 matrix, it says that it is not possible to solve:

[ 0 0 0 0 0 0 0 0 0 0 0 ]

[ 53 207 256 207 231 348 348 348 231 244 244 ]

[ 240 33 67 33 56 133 133 133 56 33 33 ]

[ 460 107 200 107 122 324 324 324 122 33 33 ]

[ 167 340 396 340 422 567 567 567 422 442 442 ]

[ 167 367 307 367 433 336 336 336 433 158 158 ]

[ 160 20 37 20 31 70 70 70 31 22 22 ]

[ 200 307 393 307 222 364 364 364 222 286 286 ]

[ 33 153 152 153 228 252 252 252 228 78 78 ]

[ 93 140 185 140 58 118 118 118 58 44 44 ]

[ 0 7 22 7 19 58 58 58 19 0 0 ]

[ 67 153 241 153 128 297 297 297 128 39 39 ]

[ 73 253 389 253 253 539 539 539 253 36 36 ]

[ 173 267 270 267 322 352 352 352 322 231 231 ]

C++ code for creating the array: (in case someone wants to test it by using the C++ example i provided)

int r[14*11] ={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53, 207, 256, 207, 231, 348, 348, 348, 231, 244, 244, 240, 33, 67, 33, 56, 133, 133, 133, 56, 33, 33, 460, 107, 200, 107, 122, 324, 324, 324, 122, 33, 33, 167, 340, 396, 340, 422, 567, 567, 567, 422, 442, 442, 167, 367, 307, 367, 433, 336, 336, 336, 433, 158, 158, 160, 20, 37, 20, 31, 70, 70, 70, 31, 22, 22, 200, 307, 393, 307, 222, 364, 364, 364, 222, 286, 286, 33, 153, 152, 153, 228, 252, 252, 252, 228, 78, 78, 93, 140, 185, 140, 58, 118, 118, 118, 58, 44, 44, 0, 7, 22, 7, 19, 58, 58, 58, 19, 0, 0, 67, 153, 241, 153, 128, 297, 297, 297, 128, 39, 39, 73, 253, 389, 253, 253, 539, 539, 539, 253, 36, 36, 173, 267, 270, 267, 322, 352, 352, 352, 322, 231, 231};

If I run my implementation to reduce the number of zeros (so they can get covered by the minimum number of lines- step 9 in wikihow's link provided at the top -) I get the following matrix where i have to find the 0 combination unique for row and column.

The problem is that it is impossible to solve since the columns 10 and 11 (the ones bold) only have one 0 each one and it is in the same row.

Row 1 : [ 240 140 225 140 206 339 339 339 206 215 215 0 0 0 ]

Row 2 : [ 254 0 37 0 43 58 58 58 43 38 38 67 67 67 ]

Row 3 : [ 0 107 158 107 151 206 206 206 151 182 182 0 0 0 ]

Row 4 : [ 0 253 245 253 304 235 235 235 304 402 402 220 220 220 ]

Row 5 : [ 300 27 56 27 11 0 0 0 11 0 0 227 227 227 ]

Row 6 : [ 300 0 145 0 0 230 230 230 0 284 284 227 227 227 ]

Row 7 : [ 80 120 188 120 176 269 269 269 176 193 193 0 0 0 ]

Row 8 : [ 207 0 0 0 151 143 143 143 151 96 96 167 167 167 ]

Row 9 : [ 229 9 95 9 0 110 110 110 0 159 159 22 22 22 ]

Row 10 : [ 147 0 40 0 148 221 221 221 148 171 171 0 0 0 ]

Row 11 : [ 240 133 203 133 187 282 282 282 187 215 215 0 0 0 ]

Row 12 : [ 189 3 0 3 94 58 58 58 94 192 192 16 16 16 ]

Row 13 : [ 367 87 36 87 153 0 0 0 153 379 379 200 200 200 ]

Row 14 : [ 194 0 82 0 11 115 115 115 11 112 112 127 127 127 ]

Is there any kind of limitation with this method? Or is just me, making a bad implementation of the algorithm? In this case, why "is the supposed to work" example not working either?

Any suggestion would be appreciate, or if you know any trick or suggestion to help finding the minimum number of lines to cover zeros, please let me know.

Thanks in advance,

Answer 1

Is there any kind of limitation with this method? Yes. That line drawing method will only properly work if you have made the maximum number of assignments at each step. I don't particularly feel like working this out by hand to prove it, but I assume that the code you are using does not accomplish that for this particular matrix. I decided to work it out (aka procrastinate) as best as I can figure from the lack of documentation, and it doesn't actually have a problem with covering all zeroes with the minimum number of lines. It's just bad at making assignments.

Every implementation of the Hungarian Algorithm I have found online will not work. They unfortunately all copy each other without actually learning the math behind it, and thus they all get it wrong. I have implemented something similar to what Munkres describes in his article "Algorithms for the Assignment and Transportation Problems", published in 1957. My code gives the results: (0,1), (1,3), (2,8), (3,2), (9,12), (10,11), (4,9), (8,7), (5,10), (6,6), (7,0) for a minimum cost of 828.

You can view my code here: http://www.mediafire.com/view/1yss74lxb7kro2p/APS.h

ps: Thanks for providing that C++ array. I wasn't looking forward to typing it myself.

pps: Here's your matrix, properly spaced:

  0   0   0   0   0   0   0   0   0   0   0
 53 207 256 207 231 348 348 348 231 244 244
240  33  67  33  56 133 133 133  56  33  33
460 107 200 107 122 324 324 324 122  33  33
167 340 396 340 422 567 567 567 422 442 442
167 367 307 367 433 336 336 336 433 158 158
160  20  37  20  31  70  70  70  31  22  22
200 307 393 307 222 364 364 364 222 286 286
 33 153 152 153 228 252 252 252 228  78  78
 93 140 185 140  58 118 118 118  58  44  44
  0   7  22   7  19  58  58  58  19   0   0
 67 153 241 153 128 297 297 297 128  39  39
 73 253 389 253 253 539 539 539 253  36  36
173 267 270 267 322 352 352 352 322 231 231

Answer 2

Note in the link you provide section (2) that you add dummy rows or columns to make sure the matrix is square.

Now that you have a square matrix, there are a large number of different matchings which link together each row with its own column and vice versa. The solution, or solutions, is simply one of these matchings that has the lowest possible cost, so there should always be a solution.