Modelos de optimización lineal entera y aplicaciones a la minería

Abstract

El tema principal de esta memoria es el estudio del problema de planificación minera, junto con el análisis detallado de un nuevo algoritmo propuesto en la literatura para resolverlo. El problema de planificación minera consiste en determinar la secuencia de extracción de una mina a tajo abierto. Para esto, típicamente se modela la mina como un conjunto de bloques y se diseña un calendario tentativo de su extracción. En la industria minera se resuelve este problema siguiendo una serie de pasos consecutivos que terminan por entregar una planificación. Por otro lado, existen distintos modelos de optimización que han sido propuestos para resolver este problema, pero debido a que las instancias son de gran tamaño, obtener soluciones requiere de técnicas y algoritmos más elaborados. Una instancia típica posee millones de variables y millones de restricciones. Por estas razones resulta ser un problema desafiante y con una aplicación muy importante, para el cual distintos tipos de descomposiciones han sido propuestas para resolverlo, junto con pre-procesos, heurísticas o versiones simplificadas de manera de hacer el problema más manejable. Todas estas técnicas pueden resolver problemas del orden de 200.000 bloques, lo cual es bueno, pero está lejos de poder resolver problemas reales. Recientemente, Chicoisne et. al. (Operations Research, 2012) desarrollaron un algoritmo eficiente capaz de resolver instancias con millones de bloques, pero en una versión simplificada del problema. Y por otro lado, Bienstock y Zuckerberg (Optimization Online, 2009) propusieron otro algoritmo, el cual es capaz de resolver eficientemente instancias de millones de bloques y bajo ningún supuesto importante. Este último resulta ser un algoritmo muy ingenioso y será el foco principal de este trabajo estudiarlo. En el desarrollo de este trabajo se estudió principalmente el problema de planificación minera, junto con la implementación del algoritmo de Bienstock y Zuckerberg. Además, usando algunas técnicas originales y otras técnicas clásicas, se diseñaron una serie de mejoras al algoritmo que lo hacen más eficiente, aprovechando la estructura del problema de planificación minera. Se verá que estas modificaciones producen mejoras significativas en el tiempo necesario para resolver las instancias disponibles. Y por último, y como un inicio para trabajo futuro, se propone una generalización del algoritmo a un contexto más amplio. Esta generalización se implementó para un nuevo modelo de Optimización Robusta propuesto en este trabajo para el mismo problema de minería, de esta forma dando un primer paso a una nueva manera de considerar incertidumbre en este problema.