Hungarian Algorithm - Arbitrary Choices

Question

I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover 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

For this particular scenario where no more assignment is possible cause every unassigned row or column have more than 1 zeroes, Selecting the row or column with minimum zeroes and doing arbitrary assignment in that row or column worked for me. Considering only rows for that and leaving out columns also worked (as mentioned here https://python.plainenglish.io/hungarian-algorithm-introduction-python-implementation-93e7c0890e15).

Answer 2

Once the subtraction steps have been performed on all rows and columns, like you did, there is this step in the algorithm, which requires you to find the minimum number of rows or columns you can strike out to find no more zeroes in the cells that are left over (see step 3 in the Wikipedia article). If this minimum number of strike-out rows/columns equals n, then you have arrived at a matrix where the assignments can be made at positions that all are represented by zeroes.

This is the case in your second matrix.

Then there is also this algorithm step once you have done all the possible subtraction steps: if a row or column has only one zero, that zero represents an (optimal) assignment.

I think this rule can be generalised as follows:

If i rows (or columns) each have at the most i zeroes, then i of those zeroes represent (optimal) assignments.

That rule is obvious (and utterly unhelpful) when i is n.

But for small i, this can be helpful, although the algorithm to find such rows may be time consuming. In the example problem, we find that for i = 2 the rule applies for rows 3 and 4. The rule also implies that we can bar any other assignments in the columns that contain the zeroes. This means we can write our matrix as:

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

Now the rule can be applied again to rows 1 and 2, which each now also only have 2 zeroes.

We see two sub-matrixes of only zeroes (subject of where we applied the rule):

0   0
0   0

There are two ways to make assignments:

x   0
0   x

or:

0   x
x   0

In general, for a sub-matrix with i rows and i columns, there are i! solutions if all its elements are zero, but fewer if some of them are not.

In the concreate example, there are thus 2! solutions for the bottom-left sub-matrix, and 2! for the top-right matrix, resulting in 4 possible solutions.

Conclusion

Although the above considerations may sound interesting, I don't think an algorithm that searches for such sub-matrixes will be more efficient than an algorithm that just picks assignments in an ordered fashion, and backtracks as soon as it finds it is on a wrong track. As you will need all solutions, there is no sense in starting with a certain row. Backtracking should make sure the algorithm does not waste time on choices that have no future.