Ingeniera Civil Industrial / El cambio climático puede impactar sustancialmente en el sector forestal, existen diversos estudios que demuestran que los inviernos serán más cálidos y las temporadas secas aumentarán. El objetivo de este proyecto es elaborar un método que permita incluir el factor del calentamiento global en las decisiones de producción forestal. Esto a partir de un trabajo anterior, el cual concluye que agregar incertidumbre en estos modelos aumenta el beneficio esperado a través de la inclusión de 32 escenarios climáticos, agrupados en un árbol de escenarios. El aporte de este trabajo será especificar hasta qué punto es provechoso seguir aumentando los escenarios considerados. La complejidad del problema viene dada por la cantidad de datos a utilizar, ya que al aumentar el tamaño del árbol de escenarios, los tiempos de resolución incrementan considerablemente, esto ya que los escenarios comparten etapas, que deben tener valores comunes para las variables de decisión. Así, se obtiene un plan contingente, condicional a lo que ocurra en cada etapa, teniendo siempre la mejor respuesta. La metodología considera generar los escenarios de clima basado en predicciones ya hechas en distintas estaciones meteorológicas de Portugal, país donde está ubicada la zona de estudio. Luego, se busca construir un modelo de programación lineal, donde la decisión corresponde a qué áreas de un bosque talar en cada periodo. Se busca maximizar los beneficios obtenidos según los precios que corresponden a cada escenario. Para llegar a una solución con una gran cantidad de escenarios, será necesario utilizar un algoritmo que permita simplificar la resolución, en este caso Progressive Hedging, cuyo principio es resolver a través de la descomposición por escenarios. Se estudian mejoras al algoritmo, además de opciones de reducción y agrupación de escenarios, para mejorar la eficiencia del mismo. Los resultados obtenidos indican que la utilización de Progressive Hedging ofrece una eficiencia superior para instancias de gran tamaño. Esto a partir de las instancias mayores a los 300 escenarios, y además se concluye que el número óptimo de escenarios a considerar rodea los 650, en dicho punto el costo adicional para general la solución no se ve justificado, ya que la calidad de la misma no aumenta significativamente. Por otra parte, la técnica de clustering para la reducción de escenarios resultó efectiva para mejorar aún más los tiempos de resolución, considerando su correspondiente pérdida en la calidad de la solución.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / El trabajo desarrollado en esta tesis se enmarca dentro del área de investigación de operaciones, en el campo de la optimización estocástica para un problema de planificación forestal, el cual se modela como un problema lineal de carácter mixto. El problema de planificación forestal abordado en esta tesis consiste en la maximización del valor presente del plan de explotación táctico de un conjunto de 17 bosques sujeto a incertidumbres internas (rendimiento de los diversos predios) y externas (precio de los productos y cantidad demandada de estos), incertidumbres que se representan a través de árboles de escenarios. Dentro de las principales decisiones a realizar se encuentra la construcción y/o mejora de caminos de la red interna junto a la cantidad de cada predio que será cosechada, almacenada y vendida durante cada periodo. Llevar a cabo la resolución de este tipo de problemas estocásticos bajo las técnicas de optimización tradicionales se vuelve inabordable en la medida que el tamaño de la instancia aumenta, lo que justifica la utilización de un algoritmo adecuado para alcanzar resultados en tiempos razonables. La metodología de resolución utilizada se basa en el algoritmo de descomposición por escenarios Progressive Hedging (PH) sobre el cuál se realizan una serie de ajustes según las características del problema con tal de obtener mejores rendimientos. Junto a esto, se realizan una serie de comparaciones de diversas implementaciones del mismo algoritmo con respecto a técnicas de optimización tradicionales, determinando y analizando las ventajas que ofrece PH para el problema en estudio. Se implementa una metodología de generación de árboles de escenarios basada en un modelo matemático robusto, utilizando como punto de partida un proceso estocástico para representar el movimiento de las variables aleatorias, lo que permite obtener soluciones rigurosas y de calidad. Se lleva a cabo un estudio detallado respecto a técnicas de reducción de escenarios, así como del desarrollo de una metodología de simulación que permite comparar de forma cuantitativa el rendimiento de modelos estocásticos y determinísticos, permitiendo estimar el número suficiente de escenarios que logran representar de buena manera la realidad, manteniéndose óptimo el trade-off entre calidad de solución y tiempos de cómputo involucrados. Los resultados concluyen que la utilización del algoritmo PH bajo las configuraciones y ajustes realizados ofrece rendimientos superiores a las técnicas de optimización clásicas y tradicionales para problemas estocásticos de gran escala, con la posibilidad de explotar de gran manera su implementación en paralelo, obteniéndose así rendimientos superiores en la medida que se cuente con mayores recursos computacionales. Se determinan los mejores métodos para llevar a cabo la reducción del número de escenarios de la instancia original, permitiendo así el manejo abordable de instancias que inicialmente se presentan complejas. Finalmente, la aplicación de la metodología de comparación de rendimiento entre modelos determinísticos y estocásticos fue satisfactoria, determinándose un rango para el número suficiente de escenarios a utilizar dentro del modelo en estudio de tal forma de alcanzar un punto óptimo entre calidad de la solución y el rendimiento computacional del modelo.

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / El presente trabajo, trata sobre metodologías de resolución de problemas estocásticos multi-etapa. El objetivo es comparar el algoritmo Stochastic Dual Dynamic Programming (SDDP), con la metodología Progressive Hedging (PH). La diferencia entre metodologías radica en que SDDP corresponde a un algoritmo de descomposición vertical o por períodos, mientras que PH representa una metodología de descomposición horizontal o por escenarios. El estudio se desarrolla en el contexto eléctrico chileno, caracterizado por una red eléctrica compuesta por generadores, demandas y líneas de transmisión. Además de una red hídrica; en la que se modelan todos los generadores hidroeléctricos, flujos hídricos y capacidades de almacenamiento. Para realizar las pruebas, se utilizan instancias de distintos tamaños y horizontes de planificación, bajo el supuesto uninodal (todas las centrales eléctricas y demandas, conectadas a un mismo nodo) y multinodal. Las metodologías fueron testeadas mediante un árbol en común. Los resultados muestran que en general, SDDP presenta tiempos de ejecución mucho menores, atribuibles principalmente al lenguaje de ejecución (Fortran vs Python). En cuanto a la exactitud de la solución, PH muestra un mejor desempeño, con diferencias poco significantes. Un segundo estudio, es la confrontación de generadores de árboles de escenarios. Se compara la metodología actual (nombrada PLP), con dos generadores desarrollados íntegramente en esta investigación. Estas metodologías se basan en probabilidades condicionales por período, y llevan el nombre de Synth y NSG, que corresponden a generación de escenarios sintéticos e históricos, respectivamente. Una de las ventajas de estas metodologías es que consideran tanto la correlación espacial, como la correlación temporal. Bajo escenarios extremos, Synth muestra los menores costos operativos en un 60% de las pruebas realizadas, obteniendo costos comparativos hasta un 7% menores. Por otro lado, bajo escenarios promedios, existe un desempeño muy parecido entre los generadores Synth y PLP, donde PLP muestra mayores ahorros comparativos.

Magisterská práce se zabývá stochastickou optimalizací síťových úloh. Teoretická část pokrývá tři témata - teorii grafů, optimalizaci a progressive hedging algoritmus. V rámci optimalizace je hlavní část věnována stochastickému programování a dvoustupňovému programování. Progressing hedging algoritmus zahrnuje také metodu přiřazování scénářů a modifikaci obecného algoritmu na dvou stupňové úlohy. Praktická část je věnována modelům na reálných datech z oblasti svozu odpadu v rámci České republiky. Data poskytl Ústav procesního inženýrství.

Stochastické programování a optimalizace jsou mocnými nástroji pro řešení široké škály inženýrských problémů zahrnujících neurčitost. Algoritmus progressive hedging je efektivní dekompoziční metoda určená pro řešení scénářových stochastických úloh. Z důvodu vertikální dekompozice je možno tento algoritmus implementovat paralelně, čímž lze významně ušetřit výpočetní čas a ostatní prostředky. Teoretická část této diplomové práce se zabývá matematickým a zejména pak stochastickým programováním a detailně popisuje algoritmus progressive hedging. V praktické části je navržena a diskutována původní paralelní implementace algoritmu progressive hedging, která je pak otestována na jednoduchých úlohách. Dále je uvedená paralelní implementace použita pro řešení inženýrského problému plynulého odlévání ocelové bramy a na závěr jsou získané výsledky zhodnoceny.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Quetena corresponde a un proyecto ubicado en las proximidades de la ciudad de Calama, región de Antofagasta, perteneciente al clúster Toki, comprendido por los recursos mineros de los cuerpos principales de Quetena, Genoveva, Toki y Opache. Se caracteriza por la baja ley de sus recursos, lo que implica que la variabilidad del proyecto tenga una alta sensibilidad frente al precio del cobre. Es por esto que resulta particularmente interesante evaluar económicamente su explotación incorporando la variabilidad del precio del metal. Se utilizó un modelo estocástico de optimización, que se combina con un árbol de escenarios de precios para obtener planes mineros robustos y flexibles. Este modelo estocástico resulta intratable computacionalmente por su gran tamaño y complejidad, por lo que se utiliza el método Progressive Hedging (PH) creado por Roger J-B Wets y R.T. Rockafellar, el que se basa en una resolución de descomposición por escenarios. PH se utilizó para encontrar soluciones que permitieran realizar fijación de variables, para reducir el espacio factible del modelo estocástico. La hipótesis de este trabajo es que el problema de planificación minera de largo plazo con incertidumbre en el precio del cobre, modelado estocásticamente y resuelto mediante un método de separación de escenarios, entrega planes flexibles que son contingentes al precio del mineral y que permiten mejorar los indicadores económicos del negocio. El principal resultado obtenido, es que el valor de la flexibilidad de los planes mineros aumenta cuando el precio promedio de largo plazo disminuye.

No description available.

El problema de Coordinación Hidrotérmica busca encontrar la operación óptima para un Sistema Eléctrico Mixto, combinando en la solución los efectos de las etapas futuras así como los efectos que la hidrología tiene en la operación del sistema. Los Sistemas Eléctricos mixtos corresponden a aquellos sistemas en los que operan tanto centrales de generación hidráulicas, geotérmicos, térmicas y eólicas entre otras. Un ejemplo de estos sistemas es el Sistema Interconectado Central (SIC) chileno, que en particular tiene una alta presencia de centrales hidráulicas y térmicas, en el cual en un año promedio un cuarenta por ciento de la energía viene de fuentes hidráulicas y un sesenta de fuentes térmicas. Desde el punto de vista de los costos de operación, estas dos fuentes de generación presentan importantes diferencias. Mientras los costos variables de una central hidráulica son bajos, los de una central térmica son más altos debido al combustible que requiere para la generación de energía. Por otro lado las centrales hidráulicas tienen costos de inversión más elevados que las centrales térmicas. Otra diferencia entre estas tecnologías es que las centrales hidráulicas son capaces de generar energía de acuerdo a la cantidad de agua que reciben de sus afluentes o que son capaces de almacenar (en embalses o estanques de regulación). Esta característica las hace dependientes del clima, en particular de la hidrología de una determinada zona geográfica. Debido a que no es posible predecir la hidrología, ésta se modela como una variable aleatoria. El problema de Coordinación Hidrotérmica busca la manera óptima de operar un sistema mixto en el mediano y largo plazo. Tiene una naturaleza estocástica, debido a la incertidumbre presente al modelar la operación de las centrales hidráulicas. Corresponde a un problema de gran escala que incorpora muchos elementos; centrales de generación, redes de distribución, centros de consumo y restricciones técnicas y ambientales. En el presente trabajo se desarrollan y aplican metodologías de programación estocástica para la resolución de un problema de Coordinación Hidrotérmica, en particular para un sistema de generación mixto. Se estudian técnicas de descomposición para problemas estocásticos que permitan trabajar con problemas de gran escala y se trabajan métodos de generación y selección de escenarios hidrológicos con el objetivo de representar de manera adecuada las componentes estocásticas del problema. La metodología utilizada para la resolución de este problema se basa en el algoritmo Progressive Hedging (PH). En este trabajo se busca resolver un problema de planificación eléctrica a través de PH. Sobre este algoritmo se desarrollan una serie de ajustes de acuerdo a las características especiales del problema. También se realizan comparaciones con las técnicas que se utilizan actualmente para resolver este problema y se analizan las ventajas que ofrece PH para este problema en particular. El problema de Coordinación Hidrotérmica corresponde a un problema cuadrático debido a que cuenta tanto con función objetivo cuadrática como con algunas restricciones cuadráticas. La función de costos de las centrales térmicas es modelada de manera cuadrática, así como también las pérdidas de energía en las líneas de transmisión son cuadráticas. PH es un algoritmo de descomposición por escenarios que entrega soluciones exactas para programas convexos. Funciona resolviendo sucesivas veces cada escenario por separado, penalizado por desviarse de la solución promedio. Debido a su estructura, es de naturaleza fácilmente paralelizable. Dentro de los resultados se logra solucionar el problema para una serie de instancias, incluyendo instancias de tamaño real del Sistema Interconectado Central chileno. Además se realizan comparaciones entre PH y SDDP, otro de los métodos de solución del problema, mostrando las ventajas y desventajas que PH ofrece. Finalmente se concluye que PH ofrece buenas posibilidades como metodología de solución para el Problema de Coordinación Hidrotérmica. Si bien actualmente no es competitivo, en el futuro, se pueden desarrollar implementaciones basadas en computación paralela que puedan ser competitivas con las técnicas actuales de resolución.

Ingeniero Civil Industrial / La minería, que alcanza hoy en día casi un 20% de participación en el PIB nacional, corresponde a la principal actividad económica que ha tenido Chile desde la revolución industrial. Dentro de este contexto destaca la empresa estatal CODELCO como la mayor productora de cobre a nivel mundial. Considerando el impacto que tiene la industria minera, los altísimos niveles de inversión involucrados, la larga vida útil de una mina y su complejidad, el apoyo a las decisiones mediante modelos de optimización matemáticos aparecen como altamente necesarios. Hoy en día estos modelos son capaces de planificar tanto la extracción como el procesamiento del mineral considerando sólo variables determinísticas. Una variable muy importante dentro de estos modelos corresponde al precio del cobre. Es por ello que actualmente se trabaja en la implementación de modelos de planificación de largo plazo que incorporen la estocasticidad de esta variable con el fin de evaluar proyectos mineros y así dar apoyo a las decisiones de inversión. Sin embargo, y debido a la complejidad y tamaño de los procesos, el problema estocástico es demasiado grande desde el punto de vista computacional. Para resolver esto se utiliza Progressive Hedging (PH), un algoritmo que reduce el problema estocástico en muchos sub-problemas determinísticos de menor tamaño. A pesar de esto, el tiempo necesario para su resolución puede llegar a ser del orden de días o incluso semanas. Una de las cualidades que entrega el algoritmo PH es la independencia en la resolución de los sub-problemas, lo cual puede ser aprovechado para su procesamiento en paralelo de modo de reducir los tiempos de procesamiento. En este trabajo se estudia la complejidad y factores críticos en la implementación de la paralelización, además de la ganancia esperada en súper-computadores tipo clúster. El anáĺisis algorítmico del problema da luces de que la paralelización es capaz de entregar ahorros en tiempo del orden de un 90%. Por otra parte una simulación en la escalabilidad de una pequeña implementación realizada entrega un ahorro de entre 93% y 98% dependiendo de la arquitectura de memoria del computador, compartida o distribuída, compuesto de 9 procesadores con 8 núcleos cada uno. Considerando todo lo anterior, y lo que se puede observar con más detalle en este trabajo, la utilización de PH en paralelo es un camino tentador a seguir si lo que se pretende es incluir la estocasticidad de una variable como el precio del cobre en el modelo de planificación minera de largo plazo.

The projected and current adoption rates of electric vehicles are increasing. Since electric vehicles require that they be recharged continually over time, the energy needs to support them is immense and growing. Given existing infrastructure is insufficient to supply the projected energy needs, models are necessary to help decision makers plan for how to best expand the power grid to meet this need. A successful power grid expansion is one that enables charging stations to service the electric vehicle community. Thus, plans for power expansion need to be coordinated between the power grid and charging station investors. The infrastructure for the charging stations has to also be resilient and reliable to absorb this increase in load. Charging stations therefore should be included in the plans for post power disruption planning. In this work, two two-stage stochastic programming models are developed that can be used to determine a power grid expansion plan that sup- ports the energy needs, or load, from an uncertain set of electric vehicles geographically dispersed over a region. Another three-stage stochastic programming model is presented, where the decisions are made first to select which charging stations to install and expand uninterruptible power supply units and renewable energy sources. Then, when the disrup- tion occurs in the second-stage, repairs in power system and charging stations take place ahead of the arrival of panicked population to prepare for the expected surge in power de- mand. Finally, as demand is unveiled, managerial and operational decisions at the charging stations are made in the third-stage. To solve the mathematical models, we utilize hybrid approaches which mainly make use of Sample Average Approximation and Progressive Hedging algorithm. To validate the proposed model and gain key insights, we perform computational experiments using realistic data representing the Washington, DC area. Our computational results indicate the robustness of the proposed algorithm while providing a number of managerial insights to the decision makers.