Relajación y heurística Lagrangiana. Aplicación a un problema de optimización combinatoria

Abstract

La optimización combinatoria es un campo de las matemáticas en el que se trabaja con un problema modelizado de modo que el objetivo que se tiene es minimizar o maximizar una función. Las variables de ese problema están sujetas a una serie de restricciones que nos complican su resolución, entre las que se encuentran las restricciones de variables enteras. Realizaremos una pequeña introducción a los problemas de optimización relajados, cuyo nombre proviene de ser más ¨permisivos" con las restricciones, profundizando concretamente en la denominada relajación Lagrangiana. Gracias a las características de la función Lagrangiana, es posible emplear el algoritmo subgradiente para buscar un óptimo de esta función iteración tras iteración. Detallaremos los pasos y parámetros necesarios para este método, describiendo detalladamente una de las reglas más famosas, la de Held-Wolfe-Crowder. Se presentarán técnicas heurísticas con las que podremos obtener soluciones para la primera iteración del algoritmo, además de su posible mejora con una determinada frecuencia. La técnica de combinar la relajación y la heurítica Lagrangiana nos permitirá obtener simultáneamente buenas cotas inferiores y superiores del óptimo del problema original. Por último, se ha procedido a aplicar todo lo recogido en la memoria para la resolución de un problema de optimización combinatoria en particular, el problema de cubrimiento máximo. Para ello se ha empleado el programa informático de Xpress IVE y se presentan los resultados y conclusiones obtenidas del análisis de un conjunto de datos.