Desarrollo e Implementacion de Cortes en el Problema de Knapsack con Precedencias para Mejorar el Rendimiento en la Obtencion de Soluciones Enteras

Abstract

La industria minera del cobre forma un pilar fundamental en la economía de Chile y representa el 13% del PIB; además se abastece el 30% de la demanda a nivel mundial. Esta industria utiliza generalmente dos metodologías de explotación sobre los yacimientos: minería a cielo abierto y subterráneo. Ambas exhiben una gran complejidad en sus operaciones, lo que incide en la planificación de mediano y largo plazo. En esta tesis se trata el problema de la planificación de la extracción con secuenciamiento sobre un yacimiento que será explotado por una minería a cielo abierto. El modelo del secuenciamiento, se describe por: restricciones de capacidad de explotación; restricciones de precedencias, que inducen los segmentos de material que se deben extraer para alcanzar el depósito; y la naturaleza binaria de las variables de decisión que determinan: cuándo y cuál segmento de material se debe o no se debe explotar. La solución de este problema tiene como objetivo maximizar el valor presente neto del yacimiento. Sin embargo, obtener esta solución para los yacimientos reales es complejo, ya que el modelo de estos depósitos, exhiben una gran cantidad de restricciones y variables de decisión. Luego, para obtener una buena solución, se relaja la integralidad de las variables, y se mejora sucesivamente el problema relajado en base a desigualdades válidas fortalecidas (cortes). Lo anterior permite obtener una solución más cercana a la solución entera óptima, y a su vez un mejor valor presente neto del yacimiento. La metodología que se utilizó para refinar el modelo relajado se basó en la teoría de separación que fue introducida por Gomory en 1969. Esta teoría permite inferir desigualdades válidas que satisfacen las condiciones de integralidad del problema de optimización entera, pero que son inadmisibles para la solución relajada. Cuando estas desigualdades se agregan al problema relajado de forma sucesiva, se obtiene cada vez una nueva solución que se aproxima más a la solución entera óptima. En esta tesis se implementaron dos procedimientos para inferir las desigualdades. El primero, consiste en inferir una colección de desigualdades, en función de una técnica que considera de manera explícita el secuenciamiento del problema de optimización; y el segundo, determina una colección de cortes a partir del proceso constructivo de transformar un modelo con secuenciamiento a un modelo sin secuenciamiento. Cada procedimiento se aplicó de forma independiente y simultánea sobre un conjunto cuantioso de instancias de yacimientos simulados. Sobre esta colección se computaron dos métricas de calidad. La primera, estima la aproximación del modelo relajado mejorado respecto del modelo original; y la segunda, estima el cierre del gap entre las soluciones emitidas por ambos modelos. Ambas métricas se representan en gráficos de desempeño, para evaluar y analizar el valor promedio del rendimiento; y el comportamiento general que tuvo cada configuración. En base a los resultados de yacimientos simulados y respecto de la mejor configuración de corte; se computó que el cierre promedio del gap alcanzó el 53.84 %; y la aproximación promedio del modelo relajado mejorado respecto del original alcanzó el 99.26 %.