Resumen

En esta tesis se trabaja con el problema de coloreo propio de aristas con distinguibilidad por suma. Se propone una solución a dicho problema utilizando un enfoque de programación lineal entera. El objetivo del presente estudio es desarrollar un algoritmo Branch and Cut que resuelva el problema de la manera más eficiente posible. Bajo esta premisa, se exponen dos formulaciones de programación lineal entera diferentes que son comparadas para elegir la de mejor performance. Una vez determinado el mejor modelo, se exponen una heurística inicial, planos de corte basados en desigualdades válidas encontradas para dicho modelo y una heurística primal con el fin de potenciar al algoritmo. Asimismo, se realiza un análisis comparativo entre el método exacto propuesto y dos heurísticas, una búsqueda local y otra basada en un esquema de búsqueda tabú. Finalmente, se expone el mismo estudio para la implementación de un algoritmo Branch and Cut eficiente pero enfocado en una versión relajada del problema, junto con un análisis comparativo de los resultados de la versión relajada y los de la versión original.