High performance computing in deterministic global optimization

Resumen

A diario, uno debe tomar una decisión entre un abanico de posibilidades que tienen un carácter dinámico en ciertas ocasiones. Las decisiones que se toman hoy influencian las posibilidades del mañana. A través de modelos de toma de decisiones, se optimiza una función objetivo dentro de unos requisitos expresados en forma de restricciones. Al contrario que los métodos probabilistas, el uso de métodos deterministas de búsqueda exhaustiva permite resolver tales modelos con una precisión garantizada. El principal inconveniente de los métodos deterministas es que requieren un esfuerzo computacional alto que conlleva tiempos de ejecución largos. En este caso, la computación de altas prestaciones desempeña un papel muy importante para hacer abordable la solución de problemas de forma determinista. El paralelismo es necesario, no sólo para acelerar el tiempo de respuesta de un algoritmo, sino para resolver problemas cuyos requisitos computacionales sobrepasan los recursos ofrecidos por los ordenadores de sobremesa. Esta tesis doctoral tiene como objetivo el estudio y el análisis de los aspectos tanto matemáticos como computacionales relacionados con los métodos deterministas para resolver problemas de optimización global en paralelo. En concreto, se abordarán problemas que tengan una relación directa con la investigación operativa. El principal objetivo es explotar todo el potencial que un supercomputador nos ofrece. Para alcanzar esta meta, en este trabajo se estudia la mejora y posterior paralelización de dos métodos deterministas que resuelven problemas de optimización global: ramificación y acotación, y programación dinámica estocástica. Los algoritmos serán estudiados desde un punto de vista computacional. El principal objetivo de este estudio es mostrar cómo este tipo de problemas puede ser resuelto en un tiempo razonable usando técnicas de computación de altas prestaciones. El Capítulo 1 introduce el concepto de optimización global, así como los métodos anteriormente mencionados. Además, proporciona una breve revisión acerca del estado actual de la computación en paralelo. En la Parte I, se tratarán los algoritmos de ramificación y acotación para la resolución de dos problemas de distinta índole. El primer problema está relacionado con el diseño de mezclas para dos productos que comparten materias primas escasas. El algoritmo secuencial se explica en el Capítulo 2. En el Capítulo 3, se muestran varias versiones paralelas para acelerar los algoritmos presentados en el Capítulo 2. El segundo problema está relacionado con la optimización global multidimensional usando constantes con respecto a la información global sobre la estructura de los casos a resolver. Aspectos como la división del espacio de búsqueda y la estrategia de búsqueda se muestran en el Capítulo 4. La evaluación del espacio de búsqueda puede ser llevada a cabo en paralelo. El Capítulo 5 expone una solución híbrida, combinación de MPI y Pthreads, que es diseñada para un clúster de procesadores multi-núcleo. En la Parte II, se investiga el control dinámico de los semáforos, de tal forma que el tiempo de espera de los vehículos en un cruce dado sea el mínimo posible. En el Capítulo 6, se implementa en C un proceso de decisiones de Markov que genera tablas de control de tráfico para cruces regulados por semáforo y para dos cruces conectados entre sí. El Capítulo 7 analiza el espacio de estados y la posible agrupación de estos para resolver casos donde la memoria RAM requerida es mayor que la disponible en un ordenador de sobremesa. El Capítulo 8 reúne las conclusiones obtenidas durante la elaboración de esta tesis doctoral.