Optimización en problemas de tomografía electrónica y localización de concentradores con asignación única optimization in electron tomography and single-allocation hub location problems

Abstract

En esta tesis doctoral se abordan problemas de optimización matemática procedentes de dos áreas principales: Tomografía Electrónica y Teoría de Localización. Por este motivo, este manuscrito se puede dividir en dos grandes bloques. En el primero, se han desarrollado una amplia gama de herramientas y procedimientos de Programación Matemática para ser aplicadas en diferentes problemas de optimización en el área de la Tomografía Electrónica. El segundo bloque se centra en el estudio de problemas englobados dentro de la Teoría de Localización, concretamente en los problemas de localización de hubs, proponiendo nuevas formulaciones y desarrollando procedimientos de resolución eficientes, que comparados con el estado del arte en esta materia, han tenido un comportamiento bastante competitivo. El primer capítulo de este manuscrito proporciona una breve introducción sobre Tomografía Electrónica y Teoría de Localización, a través de una revisión de los conceptos básicos que aparecen en los problemas de ambas áreas. Como se ha comentado anteriormente, el primer bloque de esta tesis está centrado en el estudio de diferentes problemas de optimización en el área de Tomografía Electrónica. Este bloque incluye los Capítulos 2, 3 y 4. El Capítulo 2 analiza la resolución de problemas de reconstrucción de imágenes de Tomografía Electrónica utilizando herramientas de Programación Matemática. Estos problemas son fundamentales en este área de estudio para el desarrollo de nuevos materiales a partir del análisis de su morfología a escala nanométrica (10^-7cm), ya que sus propiedades físicas y químicas dependerán en gran medida de las estructuras observadas en las reconstrucciones obtenidas. Para ello, se plantea una formulación matemática del problema basada en el uso de la norma l1. Las reconstrucciones a través de este modelo proporcionan imágenes de mayor calidad que las adquiridas a través de los algoritmos de reconstrucción más avanzados en este área. Además, debido al alto coste computacional que presenta la resolución de los modelos propuestos a través de un solver convencional, se utilizan diferentes herramientas de Programación Matemática con el fin de desarrollar un procedimiento de resolución eliminando variables y restricciones del modelo basadas en el uso de la relajación lagrangiana. El Capítulo 3 analiza otro tipo de problema dentro del área de la Tomografía Electrónica. Dicho problema consiste en la búsqueda de una segmentación óptima de imágenes obtenidas a través de un microscopio electrónico. Básicamente, se busca un agrupamiento de píxeles que componen las imágenes de tomografía en función de sus intensidades. Este tipo de problemas resultan de gran interés dentro de la Tomografía Electrónica puesto que constituyen una pieza fundamental en el proceso de análisis de las propiedades de los materiales estudiados a partir de su morfología permitiendo identificar las diferentes estructuras que componen dichos materiales. Varias formulaciones del problema de la mediana ordenada han sido desarrolladas a lo largo de este capítulo para su aplicación en la segmentación de imágenes. La gran flexibilidad que presenta la función objetivo de los problemas de mediana ordenada, a través de diferentes elecciones de peso, permite una mejor adaptación a las diferentes estructuras de los problemas a tratar. Las segmentaciones proporcionadas por las formulaciones analizadas han sido comparadas con los métodos de segmentación más populares utilizados en la literatura, obteniendo unos resultados muy prometedores. El Capítulo 4 continúa con la aplicación de modelos de la mediana ordenada a problemas de segmentación de imágenes. Como se ha mostrado en el capítulo anterior, estos modelos proporcionan una segmentación con una calidad muy alta. Sin embargo, presentan el inconveniente de que necesitan un excesivo tiempo computacional para proporcionar segmentaciones de imágenes con un número elevado de intensidades. Por ello, en este capítulo se han desarrollado diferentes métodos heurísticos con el fin de obtener una solución a este tipo de modelos, que mantenga un equilibrio entre el tiempo de cómputo y la calidad de la segmentación generada. La eficiencia de los algoritmos considerados en este capítulo se evalúa realizando un amplio estudio comparativo de las soluciones obtenidas con estos métodos heurísticos y con las formulaciones expuestas en el capítulo anterior. El segundo bloque de esta tesis, Capítulos 5, 6 y 7, aborda problemas de localización de hubs. En el Capítulo 5 se propone una nueva formulación para resolver problemas de localización de hubs con asignación única, la cual utiliza un número menor de variables que las existentes en la literatura. Esta formulación es reforzada con varias familias de desigualdades válidas. Para algunas de estas familias se han desarrollado métodos de separación que han sido incluidos como cortes en el árbol de ramificación. Una de las ventajas que presenta tanto la formulación como el procedimiento de resolución es que no necesitan una estructura particular sobre los costes. Estos pueden no representar distancias e incluso no satisfacer la desigualdad triangular. Además, estos pueden ser dados de forma agregada o desagregada (el coste origen-destino viene dado por el coste de origen a primer hub, más el coste entre hubs, más el coste del segundo hub al destino). El Capítulo 6 analiza el caso en el que existe incertidumbre en algunos de los datos de entrada en el problema de localización de hubs tratado en el capítulo anterior. Esta incertidumbre se modela a través de un conjunto de escenarios con una probabilidad de ocurrencia para cada uno de ellos. Además, en el problema propuesto se considera que la localización de los hubs no varía para cada escenario, pero sin embargo las asignaciones sí pueden cambiar de un escenario a otro, reflejando la diferencia entre decisiones estratégicas y tácticas. En el capítulo se prueba que algunos de estos problemas se pueden reducir a la versión determinista del problema clásico de localización de hubs con asignación única. Para obtener las soluciones de las instancias de forma competitiva se incluyen diferentes desigualdades válidas y sus respectivos procedimientos de separación para generar cortes que son incorporados al árbol de ramificación. El capítulo finaliza con un amplio estudio computacional para analizar la eficiencia de la metodología de resolución con respecto a resultados existentes en la literatura. El Capítulo 7 desarrolla diversas formulaciones centradas en resolver el problema de localización de hubs con mejoras en las aristas. Estas mejoras permiten disminuir el coste de transporte de conexiones entre orígenes/destinos (O/D) y hubs, así como conexiones entre hubs con el fin de reducir el coste total de transporte de todos los envíos O/D. En el caso de que la desigualdad triangular se cumpla para los costes, el envío desde un origen hacia cualquier destino deberá utilizar como máximo dos hubs para minimizar costes. Sin embargo, las mejoras en los costes de atravesar las aristas pueden dar lugar a que la desigualdad triangular no se verifique y por tanto, se podría reducir costes utilizando más de dos hubs entre un origen y un destino. Las formulaciones se desarrollan en primer lugar para el caso de redes completas, es decir, redes en las que todas las posibles conexiones están disponibles para ser utilizadas. Tras ello, estas formulaciones son adaptadas a redes incompletas, donde además de determinar las conexiones a mejorar, el objetivo es diseñar una red para conectar los hubs de forma que se minimice el coste total de transporte. Finalmente, las conclusiones y futuras líneas de trabajo son expuestas en el último capítulo de esta tesis doctoral.