Ventajas de la descomposición dual (lagrangiana) de un problema de LP relajado

Question

Soy principiante en optimización y modelos gráficos. Lo que entiendo es que un Programa Lineal constituye una relajación y por lo tanto es una cota inferior de un Programa Lineal Entero dado. También entiendo que una relajación lagrangiana es otra forma de relajación y, por lo tanto, produce otra cota inferior. Entiendo que la cota inferior lagrangiana es siempre al menos tan buena como la cota inferior de la relajación del programa lineal (corrección hecha después de los comentarios). Lo que no entiendo es lo siguiente:

¿Hay alguna ventaja en hacer una descomposición dual de un programa lineal? Me encontré con este tutorial / conjunto de diapositivas http://www.cs.cityu.edu.hk/~cheewtan/CS8292Class/Lec13.pdf donde se realiza la descomposición dual (Lagrangeana) de LP.

¿Cuál es la ventaja de hacerlo? Estoy pensando que si tengo un ILP, ¿tendría sentido hacer primero la relajación del LP y luego la descomposición dual del LP? En caso afirmativo, ¿por qué? ¿Por qué no sería más beneficioso hacer una descomposición dual (lagrangiana) a partir de un ILP directamente, ya que proporciona un límite inferior más estricto?

Lo siento si la pregunta es tonta, pero parece que estoy confundido.

Answer 1

En primer lugar, la relajación lagrangiana no produce necesariamente un límite más estricto que la relajación lineal. En algunos casos, ambas relajaciones producen límites equivalentes (por ejemplo, si la matriz de restricciones que no se relajan es totalmente unimodular). Lo que sí se puede afirmar es que la relajación lagrangeana siempre es al menos tan buena como la lineal.

A nivel práctico, la relajación lagrangiana es más difícil de aplicar.

Dicho esto, la ventaja de hacer una relajación lagrangiana es que, si se hace correctamente (si se relaja el conjunto correcto de restricciones), producirá un mejor límite y, por lo tanto, potencialmente acelerará la convergencia.

Estos métodos de descomposición se utilizan normalmente para programas enteros, como has mencionado, pero también funcionan para programas lineales puros. Sin embargo, no estoy seguro de por qué querría hacerlo, ya que los programas lineales son fáciles de resolver. Tal vez sea interesante desde una perspectiva puramente teórica.