Resolución distribuida de problemas de optimización estocástica

Resum

En esta tesis se aborda el empleo de entornos de cálculo grid para la resolución de problemas de optimización estocástica, De forma más concreta, se considera el caso en el que la estocasticidad está representada por medio de un árbol de escenarios. Para afrontar el crecimiento del tamaño del problema de optimización que es consecuencia de la mejor representación de la incertidumbre, en esta tesis se recurre a técnicas de descomposición basadas en la descomposición de Benders. Los entornos grid están habitualmente formados por equipos heterogéneos cuya disponibilidad no puede ser asegurada. Para adecuarse a estas características, en esta tesis se propone un método de descomposición especialmente pensado para entornos grid: la descomposición por escenarios completos. Este método formula subproblemas independientes entre sí que no tienen que respetar precedencias en su resolución, lo que permite aumentar el rendimiento del grid. Además se analizan otros métodos clásicos de descomposición, como la descomposición por nodos, la descomposición por escenarios y la descomposición por subárboles. Para este último método, en esta tesis se propone una nueva estrategia de formulación de los subárboles que favorece la convergencia del algoritmo de resolución. Asimismo, se estudia el problema de asignación de los nodos del árbol de escenarios a los subproblemas fruto de la descomposición. Esta asignación se generaliza mediante la analogía con el problema de la partición de grafos, cuyo modelado se estudia en detalle. Como principal caso de aplicación de estas técnicas, en esta tesis se considera el problema de coordinación hidrotérmica. Éste es un problema de medio plazo que propone programas de funcionamiento óptimos para los grupos térmicos e hidráulicos de un sistema eléctrico de potencia. Para comparar las propiedades de los diferentes métodos de descomposición, se ha empleado un problema de tamaño realista como los empl