Desarrollo de Algoritmos metaheurísticos para la resolución del problema de particiones mínimas de cadenas de texto comunes (MCSP)

Dentro del de la investigación de operaciones y la ingeniería en general, los problema de optimización combinatorial tienen un rol destacado. Para estos problemas una de las técnicas más utilizadas es el uso de modelos de programación entera, los cuales tienen excelentes resultados con tamaños de problemas pequeños; pero cuando estos problemas crecen, estas técnicas fallan o pierden calidad respecto a otras aproximaciones.

El proyecto buscó el desarrollo de algoritmos eficientes para obtener mejores soluciones que las publicadas en el estado del arte al problema MCSP (Minimum Common String Partition ), el cual es un problema de optimización NP-hard, por lo cual la búsqueda de soluciones exactas no resulta viable. El problema MCSP es cercanamente ligado al problema de reordenamiento de génes, por lo cual tiene un interés particular en el área bioinformática.

Se logró encontrar técnicas heurísticas y metaheurísticas de optimización que se enmarca en el desarrollo tesis doctoral en la Universidad del País Vasco, institución que además provee capacidades de cómputo paralelo para las fases experimentales del proyecto.

Los resultados logrados y presentados en los artículos producidos sitúan al framework propuesto como el estado del arte para el problema MCSP y muy superior a técnicas heurísticas tradicionalmente utilizadas como también muy superior al solver CPLEX utilizado sobre la instancia original del problema.

Los resultados avalan claramente la utilidad de la hibridación utilizada sobre técnicas de programación entera, entregando un algoritmo útil para solucionar de forma práctica problemas reales y complejos en ingeniería usando herramientas computacionales estándar.