I've just started learning about the Hungarian Method. Everywhere I look, I see that the Hungarian Method gives an optimal assignment/solution to the assignment problem at hand, which I understand. However, what if there are multiple different assignments with the same (optimal) cost? After trying some examples, I found that all optimal solutions are found by the Hungarian Method. But is this generally the case?
Thank you!
A very general argument for the case with multiple optimal solutions applies here.
Consider an $n\times n$ instance of the assignment problem with multiple optimal solutions. If we pick any specific optimal solution $S$, then decrease the cost of every edge used in $S$ by a small amount $\epsilon$, then the total cost of $S$ decreases by $n\epsilon$, whereas the cost of any other optimal solution decreases by $k\epsilon$ for some $k<n$. So the same solution $S$ is the unique optimal solution for the modified problem.
If you compare what the Hungarian algorithm does in the original problem and the modified problem, then (assuming $\epsilon$ is sufficiently small) there is only one way for the algorithm to make different choices in the two cases: when it's comparing two costs that were equal in the original problem, but where one cost ended up being decreased in the modified problem.
Therefore the Hungarian algorithm, which is guaranteed to find solution $S$ for the modified problem, is also capable of finding $S$ in the original program, if it breaks ties correctly: if, whenever it compares two equal costs, it does whatever it would for the modified problem.
Since $S$ was arbitrary, it follows that for every optimal solution to the original problem, the Hungarian algorithm is capable of finding it, depending on how it breaks ties. This is a sense in which the Hungarian algorithm finds all optimal solutions.
We could actually generate all the optimal solutions by forking into two paths every time that the Hungarian algorithm has a choice between two equally good options. But if there are many ties in the cost matrix, then this could require lots of forks, and might not be efficient.