Convex metamodelling for Lagrangian cut generation in stochastic integer programs
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A medida que programación entera ha llegado a ser una herramienta de uso extendido para problemas con escala cada vez mayor, desigualdades válidas y planos cortantes han sido de importancia fundamental para optimización rápida. En este trabajo consideramos la clase de cortes Lagrangianos que surge en el campo de programación entera estocástica, desigualdades fuertes derivadas de un problema dual similares a los cortes de Benders, mas su costo computacional formidable puede ser prohibitivo. Alguna forma de aproximación es necesaria y varias propuestas existen en la literatura demostrando éxito sobre una gama relativamente limitada de programas enteros estocásticos. Proponemos una aproximación de carácter distinto conocido como metamodelación: como el cuello de botella reside en evaluaciones costosas de la función objetivo dual, la sustituimos con un regresor entrenado asignando variables duales y parámetros del problema a un valor objetivo estimado. Luego de imponer ciertos supuestos sobre la estructura del problema comúnmente observados en la práctica, se demuestra exactitud de cierta subclase de cortes Lagrangianos y adicionalmente los datos de dicho regresor son cóncavos, permitiendo uso de maquinaria de regresión convexa para entrenar modelos grandes en mayores dimensiones con escaso gasto computacional comparado con alternativas genéricas como lo son por ejemplo las redes neuronales. Un conjunto de datos para el metamodelo se genera adaptando el método cuasi-Monte Carlo, y a continuación parámetros se ajustan a través de una heurística establecida debidamente modificada para nuestros propósitos. Instancias de un problema de prueba se resuelven con dos algoritmos, el Integer L-Shaped Method (estándar para resolver programas estocásticos enteros de dos etapas) y el método de Kelley (aplicable pero inferior al anterior en el caso entero de dos etapas), encontrando que mejora sobre el primero pero se ve superado por una alternativa más simple, mientras que resultados bajo el segundo son bastante impresionantes.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2024
Keywords
Programación entera estocástica, Cortes Lagrangianos, Metamodelos, Regresión convexa, Método cuasi-Monte Carlo