| Sumario: | En el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe tener distinto color, y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores asignados en un coloreo de aristas que cumpla estas restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de grafos, que resultan una herramienta abstracta muy útil y versátil para modelar situaciones de la vida cotidiana que se quieren formalizar y resolver mediante algoritmos. Algunas variantes del problema de etiquetado de grafos han sido abordadas con éxito con técnicas de programación lineal entera basadas en la caracterización poliedral del conjunto de soluciones factibles. Bajo este enfoque, en esta tesis nos proponemos desarrollar un algoritmo tipo Branch and Cut para resolver el problema. Además, aprovechando el análisis realizado, también hacemos una propuesta algorítmica para resolver el problema que busca minimizar la cantidad de colores utilizados en el coloreo. Adicionalmente, se exploró la opción de utilizar técnicas heurísticas para resolver el problema. Las heurísticas permiten conocer asignaciones de colores factibles del problema pero, en general, no pueden determinar si son óptimas o cuan cerca están de la solución del problema. Desarrollamos tres técnicas distintas para resolver el problema: un algoritmo goloso, un algoritmo de programación por restricciones, y un algoritmo de generación de columnas. Para el desarrollo del algoritmo tipo Branch and Cut, propusimos dos modelos de programación lineal entera que evaluamos empíricamente para elegir el más prometedor, sobre el cual se realizó un estudio poliedral en profundidad. Caracterizamos la dimensión del poliedro asociado y demostramos que tres familias de desigualdades válidas definen facetas. El objetivo de realizar el estudio poliedral es entender mejor el espacio de soluciones del modelo para conseguir formulaciones más ajustadas que mejoren la performance del algoritmo. Las desigualdades estudiadas son incorporadas como cortes al modelo, para las cuales se desarrollaron algoritmos de separación que permiten agregarlas a demanda. Además, se consideraron heurística inicial, preprocesamiento y estrategias particulares de generación del árbol de búsqueda. Los resultados muestran que el algoritmo desarrollado permite resolver instancias que no son posibles de abordar utilizando las herramientas de resolución generales. Haber realizado el estudio poliedral y agregar las facetas como planos de corte resulta ser un factor determinante para afrontar instancias del problema mucho más desafiantes.
|
|---|