Development of hybrid metaheuristics based on instance reduction for combinatorial optimization problems
- PINACHO DAVIDSON, PEDRO PABLO
- José Antonio Lozano Alonso Director/a
- Christian Blum Director/a
Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea
Fecha de defensa: 14 de julio de 2017
- David Camacho Fernández Presidente/a
- Alexander Mendiburu Alberro Secretario/a
- Gabriela Ochoa Vocal
Tipo: Tesis
Resumen
La tesis presentada describe el desarrollo de algoritmos metaheurísticos híbridos, basados en reducción de instancias de problema. Éstos son enfocados en la resolución de problemas de optimización combinatorial. La motivación original de la investigación radicó en lograr, a través de la reducción de instancias de problemas, el uso efectivo de modelos de programación lineal entera (ILP) sobre problemas que dado su tamaño no admiten el uso directo con esta técnica exacta. En este contexto se presenta entre otros desarrollos el framework Construct, Merge, Solve & Adapt (CMSA) para resolución de problemas de optimización combinatorial en general, el cual posteriormente fue adaptado para mejorar el desempeño de otras metaheurísticas sin el uso de modelos ILP. Los algoritmos presentados mostraron resultados que compiten o superan el estado del arte sobre los problemas Minimum Common String Partition (MCSP), Minimum Covering Arborescence (MCA) y Weighted Independent Domination (WID).