Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / We consider risk-averse stochastic programming models for the Generation Expansion Planning problem for energy systems with here-and-now investment decisions and generation variables of recourse. The resulting problem is coupled both along scenarios and along power plants. We develop a new decomposition technique to solve the energy optimization problem, resulting from the combination of two existing procedures, one to deal with stochastic programming problems through decomposition for different realizations of the stochastic process representing the uncertain data, and the second one is a method aim to find solutions to nonsmooth optimization problems. More precisely, we combine the Progressive Hedging algorithm to deal with scenario separability, obtaining a separate subproblem for each scenario, and an inexact proximal bundle method to handle separability for different power plants in each subproblem. By suitably combining these approaches, if the evaluation errors of the proximal bundle method vanish asymptotically, then bundle method converges to an approximate solution to each scenario subproblem. Thus, under mild convexity assumptions, the Progressive Hedging algorithm generates a sequence that converges to a solution to the original problem. The methodology is satisfactorily assessed on a test instance of the Generation Expansion Planning problem, whose reduced size allows us to compare the results with those obtained when solving the problem directly, and without decomposition. / CONICYT-PFCHA/Magister Nacional/2018-22181067 y CMM Conicyt PIA AFB170001

Magíster en Gestión de Operaciones / Uno de los desafíos importantes que enfrenta un grupo de defensores corresponde a su coordinación con el objetivo de poder brindar una mayor protección al sistema que defienden. En este trabajo, se estudia el desarrollo de algoritmos eficientes y garantías de optimalidad para un modelo de juego de seguridad de Stackelberg que resuelve la coordinación de múltiples recursos defensivos descentralizados. Este modelo asume la presencia de incertidumbre en las acciones efectuadas por cada recurso defensor y la ausencia de comunicación entre ellos. En específico, el modelo de juego de seguridad de este trabajo consiste en resolver un número pequeño de problemas de programación lineal, que se pueden resolver mediante un esquema de generación de columnas. El subproblema de dicha generación de columnas corresponde a la resolución de un problema de decisión markoviana descentralizado. Estos problemas de decisión markoviana descentralizados son de difícil solución; sin embargo, es posible resolver estos subproblemas mediante heurísticas, dando como resultado un enfoque capaz de obtener soluciones subóptimas para el modelo de juego de seguridad. Se presentan diversas heurísticas para la resolución de dicho subproblema, y se realiza un estudio para evaluar su uso dentro del esquema de generación de columnas. Este estudio consiste en la simulación de instancias de prueba aleatorias para evaluar el desempeño, tanto en el valor del resultado obtenido como en el tiempo de resolución de cada heurística. Se presenta una cota para el valor óptimo de un problema de decisión markoviana descentralizado que se obtiene al resolver un problema de optimización entero relacionado. Nuestros estudios computacionales muestran que esta cota es menor a un 10% del valor óptimo. Se presentan además, variantes del enfoque de generación de columnas, buscando reducir los tiempos de solución sin sacrificar calidad de la respuesta. Estos enfoques también están basados en generación de columnas y otorgan una solución subóptima al problema planteado. Con el objetivo de evaluar el comportamiento de los enfoques presentados, se recurre a la simulación de instancias aleatorias y una instancia inspirada en parte de la red de metro de Santiago. Además, con el objetivo de poder evaluar las soluciones subóptimas otorgadas por dichos enfoques, se desarrolla un método que permite obtener garantías para la solución del problema de generación de columnas. En específico, el algoritmo desarrollado permite resolver el problema de patrullar descentralizadamente una red conformada por 16 estaciones de metro, durante 12 períodos de tiempo y utilizando 6 recursos. Esta solución se obtiene, en promedio, en un tiempo de 400 [s] y con una garantía del 20%. / Este trabajo ha sido parcialmente financiado por CONICYT-PCHA/Magíster Nacional/2015 - 22152053 Powered@NLHPC: Esta investigación fue parcialmente apoyada por la infraestructura de supercómputo del NLHPC (ECM-02)