Análisis Probabilístico de Jerarquías en Optimización Lineal

Las jerarquías de programación lineal ofrecen una manera sistemática de robustecer la región factible de una relajación lineal, y en consecuencia una potencial mejora en el gap de integralidad. Estas jerarquías tienen garantías de convergencia al valor del problema entero, sin embargo, esta convergencia podría ser muy lenta o incluso la jerarquía podría fallar en certificar infactibilidad para problemas sencillos. El objetivo de esta IPRE es estudiar el comportamiento del integrality gap en estas jerarquías para instancias aleatorias o típicas. Estos modelos probabilísticos ofrecen una salida a los distintos resultados worst-case existentes en la literatura, profundizando nuestro entendimiento respecto de las garantías de optimalidad para este tipo de relajaciones. Durante la IPRE usaremos herramientas de optimización lineal y análisis estocástico.