Efficient methodologies for the treatment of large-scale stochastic optimization problems

Resumen

El ámbito de investigación de este trabajo es La Programación Estocástica, disciplina que trata de modelizar y resolver problemas de optimización bajo incertidumbre. En general, las aplicaciones reales son de grandes dimensiones, con la complicación adicional de incluir variables 0-1. Ambas características hacen que este tipo de problemas sean difíciles de resolver. En este trabajo se pretende abrir un camino en la exploración de la obtención de soluciones factibles cuasi óptimas (en el peor de los casos) para problemas mixtos 0-1 de grandes dimensiones.Se presenta la Relajación Lagrangeana como metodología capaz de proporcionar una cota de la solución óptima. Dada la estructura del Modelo Determinista Equivalente bietapa en formulación extendida, se plantean dos descomposiciones. La descomposición que resulta al relajar las condiciones de noanticipatividad asociadas a los escenarios, y la resultante de relajar las condiciones de noanticipatividad asociadas a racimos de escenarios. A partir de la implementación de distintos procedimientos computacionales en C++ junto con los solvers COIN-OR y CPLEX integrado en COIN-OR, se han llevado a cabo varias experiencias computacionales comparando el comportamiento de diferentes metodologías para la actualización de los multiplicadores de Lagrange como son: el Método del Subgradiente, el Algoritmo del Volumen, el Progressive Hedging Algorithm y el Dynamic Constrained Cutting Plane Method; así como las dos descomposiciones propuestas y los dos solvers utilizados.Finalmente, debido a los buenos resultados obtenidos en dos etapas, se propone la extensión de dicha metodología a problemas estocásticos multietapa mixtos 0-1.