Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut

Mostrar todas las versiones(3)

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 se...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Méndez Díaz, Isabel
Otros Autores: Maculan, Nelson
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2003
Materias:
GRAPH COLORING
LINEAR
Acceso en línea: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
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n3567_MendezDiaz_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
topic GRAPH COLORING
LINEAR
spellingShingle GRAPH COLORING
LINEAR
Méndez Díaz, Isabel
Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
topic_facet GRAPH COLORING
LINEAR
description 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.
author2 Maculan, Nelson
author_facet Maculan, Nelson
Méndez Díaz, Isabel
format Tesis doctoral
Tesis doctoral
publishedVersion
author Méndez Díaz, Isabel
author_sort Méndez Díaz, Isabel
title Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
title_short Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
title_full Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
title_fullStr Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
title_full_unstemmed Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut
title_sort problema de coloreo de grafos : un estudio poliedral y un algoritmo branch-and-cut
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2003
url 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
work_keys_str_mv AT mendezdiazisabel problemadecoloreodegrafosunestudiopoliedralyunalgoritmobranchandcut
_version_ 1766015591233093632
spelling I28-R145-tesis_n3567_MendezDiaz_oai2023-04-26 Maculan, Nelson Méndez Díaz, Isabel 2003 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. The graph coloring problem, PCG, is perhaps one of the oldest and most well-known problems in graph theory. Nowadays, it arises in many applications such as scheduling, timetabling, electronic bandwidth allocation and sequencing. PCG is known to be NP-hard for arbitrary graphs. The practical importance of the problem makes neccesary to devise algorithms capable of solving, in acceptable computational times, medium to moderate instances arising in real-world applications. A lot of work has been spent in an attempt to develop efficient algorithms for the problem, mainly by using heuristic techniques to deal with large instances. Relatively few methods for solving the problem exactly can be found in the literature. Like most optimization problems on graphs, PCG can be formulated as a linear integer programming problem. LP-based Branch-and-Cut algorithms are currently the most successfull tool to deal with these models computationally. However, the amount of research effort spent in attempts to solve PCG by this method is not comparable with that devoted to other problems, like TSP or maximum stable set. If the integer programming formulation exhibits symmetries, i.e. many solutions exist with the same optimal value, it turns out that Branch-and-Cut exhibts poor performance even for small instances. The classical models for PCG suffered from this problem. In this thesis, we present new integer programming formulations that reduce the number of feasible symmetrical solutions. We develop a polyhedral study of the polytope associated with the proposed models in order to derive families of facet-defining inequalities. Branch-and-Cut implementations that take advantage of the particular structure of the problem under consideration have proved to be the most successfull. In this sense, the use of cutting planes arising from a polyhedral study of the feasible solution set allowed many instances of hard combinatorial optimization problems to be solved to proven optimality for the first time. We develop a Branch-and-Cut algorithm based on our theoretical polyhedral results. We also take into account many others factors like preprocessing, search and branching strategies, lower and upper bounds and streghthening of the LP-relaxation. We present computational results showing that our algorithm performance is successful when compared to known exact algorithms. Fil: Méndez Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n3567_MendezDiaz spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar GRAPH COLORING LINEAR Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n3567_MendezDiaz_oai

Ejemplares similares