¿Por qué es importante la holgura complementaria?

La holgura complementaria (CS) se enseña comúnmente cuando se habla de dualidad. Establece una buena relación entre las restricciones / variables primarias y duales desde un punto de vista matemático.

Las dos razones principales para aplicar CS (como se enseña en cursos de posgrado y libros de texto):

1. Para verificar la optimización del LP
2. Para ayudar a resolver el dual

Dada la potencia informática actual y los algoritmos polinómicos para resolver LPs, ¿la CS sigue siendo relevante desde un punto de vista pragmático? Siempre podríamos resolver los duales y abordar los dos puntos anteriores. Estoy de acuerdo en que es "más eficiente" resolver el dual con la ayuda de CS, pero ¿es eso? ¿O hay más en CS de lo que parece? ¿Dónde es exactamente CS útil más allá de los dos puntos anteriores ? Comúnmente he visto textos alusivos al concepto de CS cuando hablamos de algoritmos de aproximación, pero no entiendo su papel allí.

La holgura complementaria es clave en el diseño de algoritmos primarios-duales. La idea básica es:

1. $y$
2. $x$$(x, y)$
3. $x$$y$

$s$$t$$s$$t$

Los algoritmos primarios-dobles son buenos por muchas razones. Filosóficamente, proporcionan más información que un algoritmo genérico. Por lo general, dan algoritmos de tiempo fuertemente polinomiales, mientras que todavía no tenemos solucionadores de LP fuertemente polinomiales. A menudo son más prácticos que los algoritmos genéricos. Esto es especialmente cierto si no podemos escribir el LP explícitamente y nuestra única otra opción es el algoritmo elipsoide, que es el caso con el emparejamiento no bipartito y el algoritmo primal-dual de Edmonds.

$y$$x$$y$$x_i > 0$$y_j > 0$$x$$\alpha$$\alpha$