DIETHA II – Diseño, Implementación y Explotación de Técnicas Heurísticas Avanzadas

Investigador principal: Abraham Duarte. Entidades financiadoras: Ministerio de Economía y Competitividad (TIN2015-65460-C2-2-P). Duración: 01/01/2016 - 31/12/2018.

Resumen:

Existe una gran cantidad de problemas que se enmarcan en el contexto de la optimización combinatoria caracterizados por el alto interés asociado a su resolución práctica. Este proyecto aborda cinco familias distintas de problemas combinatorios. Estas son:

Problemas de ordenación: con aplicaciones en el diseño VLSI o en la resolución eficiente de sistemas de ecuaciones. Problemas de localización: con interés en aplicaciones de telecomunicaciones como la distribución de regeneradores de señal o el diseño de redes. Problemas basados en grafos: con aplicaciones en la distribución de dispositivos electrónicos en placas electrónicas o en la segmentación de imágenes. Problemas de enrutamiento: centrándose en problemas multiobjetivo con aplicaciones en el transporte de materiales peligrosos o en sistemas de recomendación. Problemas de selección: con aplicaciones en la construcción de grupos diversos o el clustering de documentos. La metodología para resolver los problemas descritos anteriormente son procedimientos metaheurísticos, entre los que destacan los algoritmos evolutivos, la búsqueda tabú, la búsqueda de vecindades variables o GRASP, por citar algunos de los más conocidos. Para cada problema combinatorio, propondremos la metaheurística más adecuada en función de su estructura o modelo matemático. Nos centraremos principalmente en el diseño de estrategias novedosas para obtener soluciones de alta calidad. Además, se espera descubrir estrategias generales que puedan aplicarse fácilmente a otros problemas relacionados. También nos centraremos en la implementación eficiente y flexible de dichas estrategias, aprovechando las características de los nuevos lenguajes de programación y los microprocesadores multinúcleo. Por último, nos centraremos en la explotación a través de una plataforma de gestión, que integra los problemas abordados anteriormente. Simultáneamente, desarrollaremos una aplicación para poner en producción (en las empresas interesadas en nuestro proyecto de investigación) los algoritmos desarrollados durante el proyecto.

Además de resolver los problemas presentados anteriormente, un segundo objetivo del proyecto es desarrollar las propias metodologías metaheurísticas. Para afrontar con éxito este reto el equipo de investigación cuenta con el investigador Nenad Mladenovic, que ha desarrollado junto con Pierre Hansen la metodología de búsqueda de vecindario variable.

Todos estos problemas se integrarán en Optsicom, una herramienta de software que permite la ejecución de algoritmos dedicados a resolver problemas de optimización y analizar los resultados asociados. Optsicom puede utilizarse a dos niveles: como usuario final o como investigador de métodos heurísticos. En esta línea, los problemas integrados en Optsicom también estarán disponibles vía web en Optsicom Repository, una plataforma web para la gestión integral de problemas de optimización. En esta plataforma se publicará toda la información asociada a un problema de optimización. Para cada problema, se espera almacenar la descripción, los algoritmos, las instancias, los resultados experimentales y las referencias relevantes. Además, los resultados obtenidos mediante la ejecución de los algoritmos pueden ser comparados utilizando diferentes pruebas estadísticas que están disponibles como parte de la herramienta de software.