Justificación del método húngaro (Kuhn-Munkres)

Escribí una implementación del algoritmo Kuhn-Munkres para el problema de coincidencia perfecta bipartita de peso mínimo basado en las notas de clase que encontré aquí y allá en la web. Funciona muy bien, incluso en miles de vértices. Y estoy de acuerdo en que la teoría detrás de esto es realmente hermosa. Y, sin embargo, todavía me pregunto por qué tuve que ir tan lejos. Me parece que estas notas de clase no explican por qué no podemos simplemente tomar el programa lineal primario y pasarlo al método simplex. Por supuesto, sospecho que es una cuestión de rendimiento predecible, pero como no lo he visto explícitamente, no estoy muy seguro. Se ha comprobado que los puntos extremos del politopo del primario están en 0-1, por lo que parece que podemos alimentarlo directamente a una implementación simple sin siquiera formular el dual. ¿O estoy siendo simplista?

(Movido de un comentario).

Por supuesto, puede resolver cualquier LP utilizando un solucionador de LP de uso general, pero los algoritmos especializados generalmente tienen un rendimiento mucho mejor.

No se trata solo de garantías teóricas de rendimiento asintótico, sino también de rendimiento práctico en el mundo real. Algoritmos como el método húngaro pueden simplificarse extremadamente y son relativamente fáciles de implementar de manera correcta y eficiente.

También puede evitar problemas como el uso de números racionales exactos frente a números de coma flotante; todo se puede hacer fácilmente con enteros.

Aunque esa respuesta es correcta en un sentido general, también es útil tratar de comprender específicamente qué falla cuando se aplica el símplex primario al problema de asignación. Considere un problema de asignación de NxN con la matriz de costo cuadrado c_ij. El LP correspondiente tiene N ^ 2 variables x_ij para resolver. Pensando en estos x_ij como una matriz cuadrada X, una solución factible requiere que X sea una matriz de permutación, que se aplica mediante restricciones 2N-1 en nuestro LP (puede parecer a primera vista que hay restricciones 2N, una para cada fila y uno para cada columna, pero no todos son independientes y descartamos uno de ellos). Las restricciones de LP forman una matriz A (2N-1) x (N ^ 2).

Ahora, se forma una solución básica eligiendo un conjunto de variables básicas (2N-1). Sin embargo, para que esta solución básica también sea factible, solo N de esas variables pueden tener el valor 1, y la otra (N-1) es 0. Por lo tanto, cada solución factible es degenerada. El problema con esta degeneración es que cualquiera de las variables básicas (N-1) que son 0 pueden intercambiarse con cualquiera de las variables no básicas (N ^ 2-2N + 1), un llamado "pivote degenerado", sin efecto sobre el valor de la función objetivo [solo está intercambiando una variable 0 por otra]. Cuando N es grande, el algoritmo primitivo simplex desperdicia mucho tiempo haciendo pivotes degenerados que no mejoran la solución. Este es el quid de por qué el ingenuo algoritmo primal simplex no se usa directamente para resolver el problema de asignación.