How to solve the assignment problem with the hungarian algorithm when there is more than one optimum solution

Question

I am trying to implement the Hungarian algorithm in Java. I am able to solve it for maticies that have a single optimum solution. However, when there is more than one optimum solution I am at a loss on how to solve it (proramatically speaking).

Take the example matrix.

3   1   1   4   
4   2   2   5   
5   3   4   8   
4   2   5   9

After performing row and column reductions. The matrix will look like.

0   0   0   0   
0   0   0   0   
0   0   1   2   
0   0   3   4   

Now there are clearly multiple solutions to this, such as

0   0   0   0*  
0   0   0*  0   
0   0*  1   2   
0*  0   3   4   

and

0   0   0*  0   
0   0   0   0*  
0*  0   1   2   
0   0*  3   4   

How does one go about programming a method that finds at least one of these solutions? Arbitrarily assigning an initial 0 will often force you into a dead end. e.g. if the 0 at position 0,0 was assigned, the following would happen.

0*  0-  0-  0-  
0-  0-  0*  0-  
0-  0*  1-  2-  
0-  0-  3-  4-  

So how do I intelligently pick optimum solution locations?

Answer 1

If you hit a "dead end" you need to look for an augmenting path, as in unweighted maximum matching algorithms. See e.g. these lecture notes.