Graduados

Tesis

La tesis está dividida en dos partes: un algoritmo para obtener cortes válidos para problemas binarios con restricciones probabilísticas y analizar modelos adversos al riesgo aplicados una versión estocástica del problema del pit final.

En la primera parte, proponemos un algoritmo basado en sistemas infactibles irreducibles para resolver problemas generales binarios con restricciones probabilísticas. Utilizando la estructura del problema, somos capaces de generar tempranamente buenas cotas superiores al valor óptimo del problema, y usamos el contexto discreto a nuestro favor para eficientemente buscar soluciones. Probamos nuestra metodología en distintas instancias de un problema de vacunas y en un problema de set covering (no sé traducirlo bien…) estocástico. En la mayoría de los casos, el número de nodos visitados se reduce drásticamente comparando el rendimiento con solvers comerciales.

En la segunda parte, nuestro trabajo se focaliza en cómo es que medidas de riesgo cambian el comportamiento de la solución de problemas mineros, específicamente en el problema de pit final estocástico, y si es que las medidas de riesgo conocidas actualmente pueden capturar el efecto de la estocasticidad del modelo de manera de hacer sentido en el contexto minero. Finalmente, desde una perspectiva algorítmica, queremos ser capaces de resolver el problema resultante con la medida de riesgo apropiada para minas reales en un tiempo razonable.

Tesis: Applications of Integer Programming and Decomposition to Scheduling Problems: the Strategic Mine Planning Problem and the Bin Packing Problem with Time Lags

En problemas de agendamiento, el objetivo es asignar tiempos a un conjunto de actividades. En estos problemas, típicamente hay restricciones de precedencias entre actividades que dictan el orden en que deben ser ejecutadas y restricciones de recursos que limitan el número que pueden ser ejecutadas simultáneamente. En esta tesis desarrollamos metodologías de programación entera mixta, basada en métodos de descomposición, para dos clases de problemas de agendamiento. Estos son el problema de planificación minera a rajo abierto (SOPMP) y el problema de bin packing con lags de tiempo (BPPTL).

Dada una representación discretizada de un yacimiento minero, conocida como modelo de bloques, el SOPMP que consideramos consiste en definir qué bloques extraer, cuándo extraerlos, y el cómo procesarlos, de forma que se satisfagan restricciones operacionales y se maximice el valor presente neto. Es sabido que estos problemas son muy difíciles debido al gran tamaño de problemas de planificación minera reales (millones de bloques, docenas de años), si bien son muy importantes para la industria minera. Cada operación minera de gran tamaño en el mundo debe resolver este problema al menos una vez al año.

En la tesis empezamos estudiando un algoritmo lagrangeano desarrollado por Dan Bienstock y Mark Zuckerberg (el algoritmo de BZ) en 2009 para resolver la relajación LP de instancias grandes de SOPMP. En este estudio generalizamos la clase de problemas que pueden ser resueltos con el algoritmo de BZ, y mostramos que puede ser visto como un tipo especial de algoritmo de generación de columnas. Probamos, para la clase general de problemas de programación entera mixta, que la relajación de BZ provee una cota que está entre la de la relajación LP y la cota de Dantzig-Wolfe. Adicionalmente desarrollamos mejoras computacionales que mejoran el desempeño del algoritmo de BZ en la práctica, y las testeamos en una colección grande de instancias.

A continuación lidiamos con el problema de computar soluciones enteras factibles de SOPMP. Usando el algoritmo de BZ desarrollado en el capítulo 2, desarrollamos heurísticas. Adicionalmente, desarrollamos algoritmos de pre-proceso que reducen el tamaño del problema, e insertamos el algoritmo de BZ dentro de un procedimiento de branch-and-cut que usa dos clases nuevas de planos cortantes. Al comparar el valor de las heurísticas con la cota de la relajación LP, el gap promedio computado es cercano a 10%. Sin embargo, al aplicar las técnicas de  pre-proceso y planos cortantes, este gap se reduce a un 1.5% en el nodo raíz. Tras cuatro horas de branche este se reduce a un 0.6%.

Finalmente, el problema de bin packing con lags de tiempo es presentado. Este es una generalización del problema de bin packing, en el que los bins deben ser asignados a períodos de tiempo, satisfaciendo restricciones de precedencia con lags de tiempo. Proponemos dos formulaciones de programación entera: una formulación compacta que modela el problema de forma exacta, y una formulación extendida que modela una relajación. Para dos casos especiales del problema, el caso con un número ilimitado de bins por período y el caso en que sólo se permite un bin por período y los lags de tiempo son no-negativos, agregamos una familia espacial de restricciones a la formulación extendida para fortalecerla. Proponemos un un algoritmo de branch-cut-and-price (BCP) para resolver esta formulación, con separación de soluciones enteras y de soluciones fraccionarias, y una heurística de strong diving. Experimentos computacionales confirman que el algoritmo BCP supera el desempeño de resolver la formulación compacta con un software de optimización comercial. Usando este enfoque podemos resolver óptimamente el 70% de una clase de instancias previamente abiertas de este problema.

Tesis: Estudio del Problema de Ruteo de Vehículos con Consistencia en el Servicio.

El problema estudiado en la presente tesis está enmarcado en la operación de un centro de distribución de una empresa de alimentos. La empresa tiene un centro de distribución y múltiples clientes distribuidos en una zona geográfica. Los clientes que realizan pedidos cambian día a día, así́ como su demanda. Además, cada cliente requiere que sus pedidos se entreguen dentro de una ventana horaria determinada. La empresa conoce la demanda de los clientes con un día de anticipación y cuenta con una flota homogénea de vehículos. Para realizar actividades de distribución diarias, cada conductor tiene asignado un conjunto de clientes fijo. Los conjuntos de clientes asignados a diferentes conductores son disjuntos. Actualmente, la empresa, en condiciones de alta demanda, no logra entregar todos los pedidos de sus clientes a tiempo. Esto se debe principalmente a la alta variabilidad en la actividad de clientes presente entre los diferentes días de operación de la empresa. Particularmente, los clientes no realizan pedidos todos los días y la frecuencia con la cual lo hacen es irregular. Por otro lado, las cantidades demandas por los clientes no son constantes y cambian entre un pedido y otro. Esto, provoca inconvenientes en el ruteo diario realizado por los conductores impactando negativamente en el nivel de servicio de la empresa.

Esta tesis se enfoca en investigar estrategias de ruteo alternativas para el problema de la empresa antes descrito, que le permitan mantener la consistencia en la asignación de conjunto de clientes a conductores, respetando las cantidades pedidas por sus clientes y sus ventanas horarias. A este problema lo llamamos Consistent Vehicle Routing Problem with Time Windows (ConVRPTW). En particular, se estudiarán estrategias de diseño de rutas que preserven los requerimientos de consistencia del servicio, que en la literatura se enmarcan dentro del Consistent Vehicle Routing Problem. También, se estudiarán estrategias de diseño de rutas que adicionalmente permitan que las rutas construidas no se intercepten entre si, que en la literatura se enmarcan dentro de los problemas de Diseño de Territorios. Finalmente, se evaluará de qué forma impactaría en los resultados de la empresa el uso de estas dos estrategias de solución.

La energía juega un papel fundamental en nuestras vidas, ya que es un insumo esencial no sólo para las tareas diarias sino también para llevar a cabo diferentes actividades productivas. Debido a la constante transformación que está experimentando el sector energético, es de vital importancia la planificación de estrategias a largo plazo que garanticen nuestro suministro de energía en el futuro. El horizonte de planificación suele ser lo suficientemente largo, es decir, de 20 a 50 años, para identificar desarrollos rentables y robustos según criterios técnicos, económicos, sociales y ambientales. Una característica inherente en estos modelos es la carencia de datos fiables y presencia de errores de medidas en los parámetros de entrada. Tales características conducen a dificultades en el análisis de la soluciones y exponen a las estrategias identificadas a un alto riesgo de ser sub-óptimas cuando el futuro se desvía del valor pronosticado.

Diferentes enfoques de optimización se han utilizado como herramientas para dar soporte al proceso de toma de decisiones ante la presencia de incertidumbre. Tanto la Programación Estocástica (SP) como la más recientemente, la Optimización Robusta (RO) han sido ampliamente utilizada para hacer frente a la incertidumbre en los modelos de energía. En resumen, SP busca la decisión que optimiza el valor esperado (o una función de riesgo más general) del objetivo, donde se calcula la esperanza con respecto a la distribución de probabilidad de las variables aleatorias que representan la incertidumbre en la problema. Debido a que tales distribuciones de probabilidad a menudo se denotan sobre un número muy grande o incluso un numero infinito de posibles realizaciones, se suelen aplicar enfoques de muestreo y/o descomposición para resolver tales problemas numéricamente. Sin embargo, una limitación bien conocida de la SP, es el conocimiento del verdadero valor de la distribución de probabilidad (PDF) y el problema de la dimensionalidad (incremento de etapas y escenarios). Por otro lado, la Optimización Robusta (RO) adopta un enfoque min-máx que aborda la incertidumbre, de manera que se pueda garantizar factibilidad ante cualquier realización los datos inciertos que varían en un conjunto de incertidumbre determinístico, el cual ha sido especificada por el usuario. La diferencia con la SP es que RO no requiere una distribución específica para cada parámetro incierto. Sin embargo, es conocido que RO puede generar soluciones muy conservadoras, el cual naturalmente incrementa el costo de las soluciones.

Esta tesis propone el uso de varios enfoques de optimización para abordar estas modelizaciones y problemas computacionales. Más precisamente, su contribución es doble. Primero, implementamos una formulación SP en dos etapas para un sistema de energía suizo presentado en la literatura, donde se consideran todas las fuentes de incertidumbre y se asumen diferentes PDF para destacar su posible impacto en las decisiones estratégicas de inversión en tales modelos a largo plazo. Luego, proponemos una novedosa combinación de Aprendizaje Automático (Machine Learning) y Optimización Robusta en Distribución (DRO) que permite obtener una formulación robusta numéricamente trazable para el mismo sistema de energía y que se espera que sea menos sensible a la elección de los PDFs. En segundo lugar, proponemos extender el modelo de dos etapas a un modelo de programación lineal estocástica multietapas (MSLP) que determina la política operativa para la planificación energética a largo plazo de manera secuencial, calculada mediante un algoritmo de Programación Dinámica Dual Estocástica (SDDP). Por otra parte, la modelización extensiva de todas las fuentes de incertidumbre como en el SP de dos etapas, puede ser no sólo inviable desde el punto de vista computacional sino también ineficiente. Por lo tanto, sólo consideramos la demanda y los costos de los recursos como inciertos en el MSLP. También, se busca comparar la calidad de la política obtenida bajo el supuesto de “stage-wise independent” con el obtenido al preservar la dependencia (ó “stage-wise dependent”). Para lograr este ultimo supuesto, proponemos una metodología para discretizar un proceso Markoviano multidimensional, de manera que las probabilidades de transición varíen en cada etapa usando una variante del método Tauchen, y pueda ser resuelta con el algoritmo SDDP en un tiempo de ejecución aceptable.

Predicción de fallas y mantenimiento prescriptivo

La industria moderna ha ido evolucionando de manera exponencial haciendo que los sistemas sean más sofisticados, con mayor funcionalidad y, por tanto, mayor número de sensores para un mejor control. Generalmente, estos sistemas son propensos a mal funcionamiento, bien sea, por defecto de fábrica, por desgaste de uso o por influencia del entorno expuesto; generando en última instancia el quiebre del sistema e inactividad inesperada de la misma en el momento de necesitarlo. Con base a esto, ha surgido la necesidad de diseñar un sistema de monitoreo que permita detectar fallas o mejor aún, que pueda predecir los momentos que pueden ocurrir las fallas en componentes o en el sistema general. En este contexto, nos referimos a una falla como la desviación no permitida de una propiedad característica del comportamiento usual de un sistema tal que garantice el buen funcionamiento, pero aún permite desempeñar por un periodo de tiempo adicional hasta el quiebre del sistema.

El diseño de este sistema de monitoreo para detección de falla generalmente requiere de mucho tiempo y ayuda humana para determinar los patrones de la falla y el ajuste del modelo que detecte una falla específica. Por lo que modelar todas las posibles fallas de un sistema complejo es casi imposible, aun limitándose a un solo tipo de falla y también, se hace más difícil si los datos son altamente ruidosos. En la actual investigación, se abordará la etapa de predicción de fallas usando técnica de machine learning que pueda lidiar efectivamente con estructuras de datos temporales permitiendo determinar patrones de manera automática. Una de estas herramientas se destacan las redes neuronales recurrentes, ya que permite preservar en su interior patrones históricas temporales y transformaciones no lineales de las entradas suministradas, haciendo que esta etapa se escalable a otros problemas sin requerir de mucho tiempo de ajustes y esfuerzo humano. Actualmente, se está aplicando el método en fallas con degradaciones lentas proveniente de los IFPs en las antenas del observatorio ALMA. Se espera aplicar en otras áreas con fallas bastante parecidas con el fin de verificar la robustez del modelo predictivo.

Por otro lado, cuando se tiene muchísimas alertas de fallas en múltiples componentes que tienen diferentes niveles incertidumbres en el tiempo de vida útil, diferentes niveles de criticidad, y distintos niveles de dificultad en un sistema complejo, como por ejemplo: el radiotelescopio ALMA que contiene 66 antenas distribuidas el desierto de Atacama que cambian de configuración y posicionamiento dependiendo del fenómeno de interés en la investigación de los expertos; hace la necesidad de ordenar y agrupar estas alertas de fallas de manera conveniente con el fin de poder diseñar un plan estratégico de mantención para que el equipo de mantenimiento pueda atender estas fallas de manera efectiva. Esta investigación aún está en proceso y se estudiarán diversas estrategias en la toma de decisiones prescriptivo para el diseño del plan estratégico en mantención con presencia de incertidumbres como las mencionadas anteriormente.