Hungarian Algorithm - Arbitrary Assignments

Question

I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover only very simplistic cases.

The most understandable explanation I've found is a YouTube video.

I can code the algorithm but I'm concerned about one special case. If you watch the video, the relevant case is explained from 31:55 to 37:42, but I’ll explain it below.

I should first mention that I will be dealing with a 300 x 300 matrix, so visual inspection is out of the question. Additionally, I need to find all minimum assignments. In other words, if there are multiple assignments that produce the same minimum value, I need to find them all.

Here's the particular case that I'm concerned about. You can see this explained in the YouTube video but I’ll go over it here. We start with this matrix:

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

When we reduce the rows and columns, we get this:

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

(Let me mention that I can visually see there are 4 solutions to this matrix and the total score is 13.)

Given the above reduced matrix, there are no unique zeros in any row or column, so, according to the algorithm described in the video, I can arbitrarily select any zero element for assignment, so I select (1,1).

I’ll mark the assigned zero with an asterisk and I’ll put an “x” next to those zeros in the rows and columns that are no longer available for consideration. Now we have this:

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

Next, we continue examining rows for a unique zero. We find one at (3,2) so we mark it with an asterisk and mark the unavailable zeros with "x":

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

Next, we start looking for unique zeros in the columns (since all rows have been exhausted). We find column three has a unique zero at (2,3) so we mark it:

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

At this point, there are no more available zeros and row 4 has been left unassigned. (This particular YouTube video now uses a “ticking procedure”, which is a common technique for determining the minimum number of lines needed to cover all the zeros. If you are unfamiliar with this technique it is explained starting at 14:10 through 16:00, although the presenter uses a different matrix than shown here.) The “ticking procedure” is this:

1. Tick all rows that have no assigned zeros (row 4).
2. For each row that is ticked, tick the columns that contain a zero in that row.
3. For each column ticked in step 2, tick the corresponding rows that have assigned zeros.
4. Repeat steps 2 and 3 until no more ticking is possible.
5. Draw lines through all ticked columns and un-ticked rows.

At this point, the ticking procedure generates 4 vertical lines, covering all zeros. The four vertical lines tell us the zeros in the matrix represent one or more solutions, yet, as we see, row 4 is unassigned. The fact that fourth row remains unassigned in spite of the four vertical lines tells us that we chose the wrong zeros for assignment!

The video’s presenter indicates this problem is a result of our initial (arbitrary) assignment of element (1,1). The presenter says, “there are more sophisticated methods available” to get us out of this situation be he does not explain what these techniques are. He alludes to the existence of “intelligent” ways of selecting a zero, rather than the arbitrary selection we used to select the zero at (1,1).

One approach I could take (I’m not sure it’s the best) when faced with making an arbitrary assignment is to make the assignment from the row or column with the fewest number of available arbitrary choices. In this example, this means I would make the arbitrary assignment from either row 3 or 4, where there are only two arbitrary choices, rather than from row 1 or 2 where there are four arbitrary choices. Of course, since I need all correct solutions, I would have to iterate over all the available arbitrary assignments, whenever an arbitrary assignment is made. For example, if I select (3,1) as an arbitrary assignment, I would also have to assign (3,2) later.

My question then, after all this, is, when I am faced with the choice of arbitrarily selecting a zero for assignment, what is the best approach? Is it what I mention in the previous paragraph? How can I eliminate the dead-end solutions like the one shown? Please remember I still need to enumerate all solutions having the same minimal score.

Answer 1

See Finding all minimum-cost perfect matchings in Bipartite graphs.

Once you run the Hungarian Algorithm, you can use the result to

1. find all "admissable" edges. Roughly speaking, admissable edges are those that are part of some min-cost perfect matching (potentially with a few extras).
2. generate perfect matchings of the subgraph of just the admissable edges. During this step, you don't need to look for min-cost perfect matchings. By the choice of admissable edges, any perfect matching of the subgraph is automatically a min-cost perfect matching of the original graph. This step is much easier than explicitly looking for min-cost perfect matchings.