Optimización lineal entera mixta aplicada a problemas de planificación estratégica en electricidad

Doctor en Sistemas de IngenieríaEn esta tesis se presentan los resultados del trabajo desarrollado por el autor durante el periodo en que fue estudiante de doctorado en el Departamento de Industrias de la Universidad de Chile. El trabajo se centra en la aplicación de técnicas de optimización entera-mixtas a problemas de planificación estratégica del sector eléctrico, donde el problema de corto plazo correspondiente al predespacho de unidades de generación en sistemas térmicos es el tema central en estudio. En lo relativo al modelamiento del problema de predespacho de unidades, se considera el análisis de las distintas formulaciones entera-mixtas disponibles en la literatura junto con una nueva basada en un formulaciones extendidas tipo red. Se investiga su desempeño sobre un conjunto de instancias reales desde el punto de vista de su eficiencia computacional al ser resueltas con softwares comerciales. Lo anterior incluye análisis de tiempos de solución, nodos utilizados e iteraciones de simplex realizadas para distintas tolerancias requeridas. Los experimentos muestran la calidad de la aproximación propuesta, siendo esta completamente competitiva respecto a las ya documentadas. Este resultado era esperable, dada la estructura totalmente unimodular de gran parte de la formulación propuesta, pero para nada justificable debido al tamaño de la misma. Lo anterior muestra que el efecto del preproceso de los softwares comerciales puede ser fundamental en algunas formulaciones. Por otro lado, respecto a la función objetivo del problema de predespacho de unidades, que por lo general se representa como una función cuadrática de la generación, se presenta una nueva manera de linealizar su comportamiento de modo que su inclusión en una formulación entera-mixta lineal tradicional sea eficiente. Esto último debe entenderse a partir de la necesidad que el tamaño de la aproximación no crezca de manera desmedida si el error requerido para la misma decrece. Si bien ya existía la posibilidad de hacer esto mediante la aplicación de la aproximación desarrollada por Ben-Tal y Nemirovsky para conos de segundo orden [2], acá se presenta un método alternativo, con mejores propiedades numéricas, un orden de magnitud mejor en calidad de aproximación, y cuya aplicación a problemas reales de predespacho de unidades genera mejores resultados respecto de las aproximaciones tradicionales. Por último, con el fin de mejorar el desempeño de la formulación entera-mixta presentada, se realiza el análisis poliedral de una de sus subestructuras esperando identificar desigualdades válidas que permitan mejorar su cota dual. Esta subestructura corresponde al knapsack semicontinuo con restricciones adicionales del tipo generalized upper bound. Se demuestra que bajo supuestos simples es posible identificar facetas tipo generalized flow cover en espacios restringidos de dimensión inferior. Luego se llevan estas desigualdades al espacio original utilizando procedimientos de lifting multidimensional independiente de la secuencia [38, 27, 16, 17] y se iii prueba que con supuestos adicionales también son facetas allí. Experimentos computacionales en instancias derivadas de problemas de UC muestran su eficiencia, donde más de un 50% del gap integral del nodo raíz se reduce aplicando en promedio solo tres de estos cortes. Además, en este contexto, también se ha implementado un solver ad-hoc para la solución eficiente de las relajaciones lineales de la formulación tipo red, con un speed-up del orden de 4x a 8x respecto a CPLEX barrier optimizer, pero que aún no está documentado