Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
El problema de coloreo de grafos, PCG, es uno de los problemas clásicos de la teoría de grafos y es estudiado desde el siglo XIX. Más allá del interés teórico, tiene una significativa importancia práctica debida a las numerosas situaciones de la vida real en las cuales surgen problemas que pueden ser modelados como un problema de coloreo de grafos. PCG pertenece a la clase de problemas NP-Hard, es decir que no se conoce un algoritmo polinomial para resolverlo. Existe en la bibliografía gran cantidad de trabajos proponiendo algoritmos para su resolución especialmente heurísticas y en menor medida algoritmos exactos. Como muchos problemas de Optimización Combinatoria, PCG se puede modelar como un problema de programación lineal entera. Los algoritmos Branch-and- Cut son la herramienta más efectiva que se conoce para resolver un modelo de programación lineal entera. En particular, las implementaciones que usan desigualdades válidas del poliedro asociado al modelo han mostrado ser las más efectivas. Tal vez una de las mayores dificultades de este abordaje se presenta cuando el problema de programación lineal entera tiene la propiedad de simetría, es decir que existen múltiples soluciones con el mismo valor de la función objetivo. En estos casos, los algoritmos habituales disminuyen en gran medida su performance. El objetivo de esta tesis es abordar la resolución del problema de coloreo de grafos mediante modelos de programación entera binaria que parcialmente eliminen soluciones simétricas. Con este fin, proponemos varios modelos que tratan la simetría del problema con diferentes criterios. Estudiamos los poliedros asociados a estos modelos y desarrollamos e implementamos un algoritmo Branch-and-Cut donde utilizamos este estudio poliedral y estrategias particulares que guían la búsqueda evitando explorar sobre soluciones simétricas. Se presentan resultados que demuestran que este algoritmo es capaz de competir exitosamente con los algoritmos exactos conocidos.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | info:eu-repo/semantics/doctoralThesis biblioteca |
| Language: | spa |
| Published: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
|
| Subjects: | GRAPH COLORING, LINEAR, |
| Online Access: | https://hdl.handle.net/20.500.12110/tesis_n3567_MendezDiaz http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3567_MendezDiaz_oai |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|