Tesis > Documento


Ver el documento (formato PDF)   Delle Donne, Diego Andrés.  "Estudios poliedrales de problemas de coloreo de grafos"  (2016-10-11)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Los problemas de coloreo de vértices surgen en una amplia gama de situaciones de la vida real. Ejemplos de ellos son los problemas de asignación de frecuencias en redes de telecomunicaciones, problemas de asignación de aulas a las materias de una universidad e incluso algunos problemas de planificación (scheduling). En general, cualquier problema de asignación de recursos a tareas que contemple incompatibilidades entre pares de tareas para usar el mismo recurso, puede ser visto como un problema de coloreo de los vértices de un grafo. Existen muchas variantes de problemas de coloreo de grafos motivadas generalmente por restricciones reales, tales como Precoloring extension, μ-coloring, (γ, μ)-coloring y List-coloring, entre otras. La programación lineal entera (PLE) ha demostrado ser una herramienta muy adecuada para resolver problemas de optimización combinatoria. En los últimos 15 a˜nos la PLE fue aplicada con éxito a problemas de coloreo de vértices recurriendo a distintas formulaciones para el problema clásico de coloreo tales como el modelo estándar, la formulación por representantes, el orientation model y la formulación por conjuntos independientes, entre otras. Si bien muchos problemas de coloreo de grafos pueden ser resueltos en tiempo polinomial en ciertas familias de grafos, la mayoría de estos problemas no está “bajo control” desde el punto de vista poliedral. Es decir, no se conocen formulaciones de programación lineal entera con descripciones completas de los poliedros asociados. En el contexto de la teoría poliedral, la equivalencia entre los problemas de optimización y separación sugiere que para estos problemas debería existir alguna formulación cuyo problema de separación asociado pueda ser resuelto en tiempo polinomial y, más aun, tal que el poliedro asociado admita una caracterización “elegante”, en términos de desigualdades lineales. La búsqueda de tales caracterizaciones es el objetivo principal del presente trabajo de tesis. El objetivo teórico es completar la contraparte poliedral de aquellos problemas de coloreo de grafos que se encuentren ya bien resueltos por medio de técnicas combinatorias. El estudio de estos poliedros puede llevarnos a un mejor entendimiento de sus estructuras permitiéndonos de esta forma encontrar nuevas familias de grafos para las cuales algunos problemas de coloreo tengan resoluci ón polinomial, aportando así nuevos resultados útiles en la práctica. De este estudio surgen también nuevas familias de desigualdades válidas que pueden incorporarse a algoritmos de planos de corte para contribuir así a mejorar su performance en la práctica. Con estos objetivos, en esta tesis estudiamos los poliedros asociados a cuatro formulaciones distintas para el problema clásico de coloreo: el modelo estándar, la formulación por representantes, el orientation model y la formulación por conjuntos independientes. Presentamos adaptaciones de algunas de estas formulaciones para distintas variantes de coloreo y en algunos casos mostramos que los problemas de optimización en los poliedros asociados son polinomialmente equivalentes al problema de optimización sobre el poliedro de coloreo clásico. Damos caracterizaciones completas de los poliedros de coloreo para grafos que surgen de ciertas operaciones. Para algunas de las formulaciones estudiadas, hallamos descripciones completas de los poliedros asociados a distintas familias de grafos, entre ellas los árboles, grafos block, split y co-interval, entre otras. Estudiamos también la relaci ón entre los poliedros de coloreo Pcol y el poliedro de conjuntos independientes STAB y mostramos que en algunos casos, el primero es una cara del segundo (o hasta coincide con éste) para un grafo asociado al grafo original. Estos resultados nos permiten obtener nuevas familias de desigualdades válidas para Pcol basadas en desigualdades válidas conocidas para STAB. Más aun, a raíz de estos resultados hallamos descripciones completas de Pcol para algunas familias de grafos en las que se conoce una descripción de STAB para el grafo asociado. Presentamos también un estudio poliedral clásico para el orientation model en el cual describimos algunas familias de desigualdades válidas que definen facetas del poliedro asociado. Basados en la estructura de estas familias, presentamos el procedimiento de path lifting, que combina dos desigualdades válidas genéricas y un camino entre dos vértices particulares y genera una familia infinita de desigualdades válidas. Mostramos que este procedimiento puede generar facetas del poliedro de coloreo asociado y damos condiciones suficientes para que esto ocurra.

Abstract:
Vertex coloring problems arise in a wide range of real-life situations. Some common examples are frequency assignment problems in telecomunication networks, classroom assignment problems at universities and even certain scheduling problems. In general, any problem consisting in the assignment of some resources to jobs with incompatibility conditions among these jobs to use the same resource can be seen as a vertex coloring problem on some graph. There exist many variants of the vertex coloring problem, usually motivated by real restrictions, such as Precoloring extension, µ-coloring, (ɣ, µ)-coloring and List-coloring, among others. Integer linear programming (ILP) has prooved to be a powerful tool to solve combinatorial optimization problems. In the last 15 years it has been successfully applied to vertex coloring problems by resorting to different formulations for the classical coloring problem such as the standard model, the representatives formulation, the orientation model and the independent set formulation, among others. Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not “under control” from a polyhedral point of view. This is, we don’t know integer programming formulations with complete descriptions for the associated polytopes. In the context of polyhedral theory, the equivalence between optimization and separation suggests for these problems the existence of integer programming formulations with polynomially-solvable separation problems and, moreover, whose associated polytopes admit elegant characterizations, in terms of linear inequalities. The search for such characterizations is the main goal of this thesis. The theoretical goal is to complete the polyhedral counterpart of those coloring problems which we know can be solved in polynomial time by means of combinatorial techniques. The study of these polytopes can lead us to a better understanding of their structures revealing some insight by which we can find new classes of graphs where vertex coloring problems are polynomial, thus contributing with new practical results. This study also yields new families of valid inequalities which may be used in cutting plane schemes, thus improving the performance on the resolution of vertex coloring problems. With these objectives, in this thesis we study four different known formulations for the classical graph coloring problem: the standard model, the representatives formulation, the orientation model and the independent set formulation. We present adaptations of some of these formulations for several variants of vertex coloring and, in some cases, we show that the optimization problems associated with the corresponding polytopes are polynomially equivalent to the optimization problem associated to the polytope for the classical vertex coloring problem. We give complete characterizations of coloring polytopes for graphs that are the product of some graph operators. For some of the studied formulations, we found complete descriptions for the associated polytopes to several classes of graphs such as trees, block, split and co-interval graphs, among others. We further study the relation between coloring polytopes Pcol and stable set polytopes STAB and we show that, in some cases, the coloring polytope for a graph G corresponds to a face of (or even coincides with) STAB( ˜G ) for a particular graph ˜G. These results allowed us to deduce new families of valid inequalities for Pcol based on valid inequalities known for STAB. Furthermore, from these results we found complete descriptions for Pcol for some classes of graphs for which STAB is known for the associated graph. We also present a classical polyhedral study of the orientation model, where we introduce new families of facet-inducing valid inequalities. Based on the structure of these families, we introduce the path lifting procedure, which combines two generic valid inequalities and a path between two particular vertices and generates an infinite family of valid inequalities for the associated polytope. We show that this procedure is able to generate facets of the polytope and we give sufficient conditions for this to occur.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Estudios poliedrales de problemas de coloreo de grafos     =    Polyhedral studies of vertex coloring problems
Autor : Delle Donne, Diego Andrés
Director : Marenco, Javier
Consejero : Bonomo, Flavia
Jurados : Méndez Díaz, Isabel  ; Pereira de Lucena Filho, Abilio  ; Argiroffo, Gabriela Rut
Año : 2016-10-11
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
Universidad Nacional de General Sarmiento. Instituto de Ciencias
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_6096_DelleDonne
Idioma : Español
Area Temática : 
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34