I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even on thousands of vertices. And I agree that the theory behind it is truly beautiful. And yet I still wonder why I had to go to such lengths. I find that these lecture notes don't explain why we can't simply take the primal linear program and pass it to the simplex method. Of course I suspect that it's a question of predictable performance, but since I haven't seen it explicitly stated, I'm not too sure. The polytope's extreme points of the primal are proven to be in 0-1, so it seems that we can feed it directly to a simplex implementation without even formulating the dual. Or am I being simplistic?
2 Answers
(Moved from a comment.)
Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance.
It is not only about theoretical asymptotic performance guarantees, it is also about practical real-world performance. Algorithms such as the Hungarian method can be extremely streamlined and they are relatively easy to implement correctly and efficiently.
You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.
Although that answer is correct in a general sense, it is also helpful to try to understand specifically what goes wrong when applying primal simplex to the assignment problem. Consider an NxN assignment problem with square cost matrix c_ij. The corresponding LP has N^2 variables x_ij to solve for. Thinking of these x_ij as a square matrix X, a feasible solution requires that X be a permutation matrix, which is enforced by 2N-1 constraints in our LP (it may seem at first glance that there are 2N constraints, one for each row and one for each column, but they are not all independent and we drop one of them). The LP constraints thus form a (2N-1)x(N^2) matrix A.
Now, a basic solution is formed from choosing a set of (2N-1) basic variables. However, for this basic solution to also be feasible, only N of those variables can have value 1, and the other (N-1) are 0. Thus, every feasible solution is degenerate. The problem with this degeneracy is that any of the (N-1) basic variables that are 0 can be swapped with any of the (N^2-2N+1) nonbasic variables, a so-called "degenerate pivot", with no effect on the value of the objective function [you are just swapping one 0 variable for another]. When N is large, the primal simplex algorithm wastes a lot of time making degenerate pivots that don't improve the solution. This is the crux of why the naive primal simplex algorithm is not used directly to solve the assignment problem.
