Resultados: visualização detalhada

Registro 1 de 1 para a busca Autor Badilla Veliz, Fernando 

Problema de Planificación Forestal Estocástico Resuelto a Traves del Algoritmo Progressive Hedging

Badilla Veliz, Fernando
Weintraub Pohorille, Andrés
Epstein Numhauser, Rafael
Ordoñez González, Fernando
Woodruff, David

2010

  • Dados de edição CyberDocs
  • Tipo de Documento Libro
  • Matéria Progrmación heurística; optimización matemática; algoritmos; explotación forestal
  • Descrição
    El objetivo de esta tesis es desarrollar un enfoque que permita maximizar el valor presente del plan de explotación de un predio forestal sujeto a incertidumbres. Las fuentes de incertidumbres son tanto internas (rendimiento: $m^3$ de madera por há) como externas (precio y cantidad demandada), y están representadas mediante escenarios. La imposibilidad de resolver este problema, a través de métodos tradicionales, al considerar muchos es ...
    El objetivo de esta tesis es desarrollar un enfoque que permita maximizar el valor presente del plan de explotación de un predio forestal sujeto a incertidumbres. Las fuentes de incertidumbres son tanto internas (rendimiento: $m^3$ de madera por há) como externas (precio y cantidad demandada), y están representadas mediante escenarios. La imposibilidad de resolver este problema, a través de métodos tradicionales, al considerar muchos escenarios, justifica el desarrollo de un algoritmo ad - hoc para lograr buenos resultados en tiempos razonables. La contribución de este trabajo es aplicar, ajustar y desarrollar una heurística basada en el algoritmo Progressive Hedging (PH) de tal manera que ya no se está limitado por el número de escenarios considerados, junto con modelar la incertidumbre del rendimiento.La metodología se enmarca en la optimización, donde dicho plan se modela como un programa estocástico entero mixto. Las decisiones binarias del modelo son cuándo y dónde cosechar rodales y construir caminos y, las decisiones continuas, cómo transportar la madera y cuánta madera vender, en cada etapa. Las incertidumbres se modelan como escenarios compuestos de etapas con valores en común, de tal manera que conforman un árbol de escenarios con probabilidades en cada ramificación. Así el resultado de resolver este problema es un plan robusto, que es condicional a los eventos que ocurren en cada etapa, siempre teniendo la mejor respuesta independiente de cual escenario ocurra.PH es un algoritmo de descomposición por escenarios que es exacto para programas lineales. Funciona resolviendo sucesivas veces cada escenario por separado, penalizado por desviarse de la solución promedio. De una naturaleza fácilmente paralelizable. Al aplicarlo con variables enteras es heurístico y es necesario desarrollar variadas técnicas y ajustes finos para lograr su convergencia. Esto se realizó en dos implementaciones: una ad - hoc en Ampl (serial) y otra usando el software Coopr que ya implementa PH de manera paralela.Los benchmarks usados en contra de este trabajo fueron: Cplex 10.2 resolviendo el problema directamente y el enfoque de B&F coordinado realizado por M.Quinteros, 2009, que considera 18 escenarios. Las instancias de prueba satisfactorias fueron: 64, 144, 162 y 216 escenarios, basados en la instancia de Quinteros (un predio real llamado 'Los Copihues'), añadiendo incertidumbre en el rendimiento del predio.Esta aplicación de PH incorporó elementos como los fortalecimientos, linearizar el término proximal cuadrático, imponer la fijación de variables binarias a través del árbol de escenarios (de acuerdo a la restricción ''hacer a lo más una vez''), para rápidamente reducir el tamaño del problema, y luego, partir Cplex con la solución encontrada por PH, completando la factibilidad de la misma. Estas y otras técnicas aceleran la resolución de los subproblemas sin perjudicar el valor de la función objetivo final y reducen el número de iteraciones totales del algoritmo.Los resultados muestran que Cplex no puede encontrar soluciones factibles si el modelo no es fortalecido. Al fortalecerlo se encuentran cotas válidas de optimalidad para comparar con las encontradas por PH (que sí es capaz de encontrar soluciones factibles incluso sin fortalecimientos). Usando Cplex fortalecido durante una hora genera un buen benchmark ($<%1.62$ gap promedio); el cual PH supera en valor objetivo por un $1%$ promedio; pero utilizando mucho menos tiempo, sólo 23 minutos promedio. Todo esto logrado con la implementación serial.Al comparar con el B&F coordinado de 18 scenarios, también se obtuvieron ganancias en tiempo, pero Cplex siempre fue mejor que ambos porque la instancia es demasiado pequeña. La implementación paralela no superó en valor a la implementación serial puesto que no implementa la fijación de variables a través del árbol según restricción. Sin embargo se logró obtener resultados acordes a los de la implementación serial, validando los resultados. También se mostró que el valor de la relajación lineal del problema es una buena cota para medir la calidad de la solución encontrada por PH.Finalmente este trabajo ha probado que PH es una heurística poderosa para obtener buenas soluciones factibles, lidiando con centenares de escenarios, en menos tiempo que Cplex, incluso sin paralelizar. Finalmente, el trabajo futuro apunta a mejorar la implementación paralela y aplicar las técnicas desarrolladas en distintos modelos de programas estocásticos enteros mixtos.
  • Identificador 14499