Estudios poliedrales de problemas de coloreo de grafos

Los problemas de coloreo de vertices surgen en una amplia gama de situaciones de la vida real. Ejemplos de ellos son los problemas de asignacion de frecuencias en redes de telecomunicaciones, problemas de asignacion de aulas a las materias de una universidad e incluso algunos problemas de planificacion (scheduling). En general, cualquier problema de asignacion 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 vertices 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 programacion lineal entera (PLE) ha demostrado ser una herramienta muy adecuada para resolver problemas de optimizacion combinatoria. En los ultimos 15 a˜nos la PLE fue aplicada con exito a problemas de coloreo de vertices recurriendo a distintas formulaciones para el problema clasico de coloreo tales como el modelo estandar, la formulacion por representantes, el orientation model y la formulacion 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 mayoria de estos problemas no esta “bajo control” desde el punto de vista poliedral. Es decir, no se conocen formulaciones de programacion lineal entera con descripciones completas de los poliedros asociados. En el contexto de la teoria poliedral, la equivalencia entre los problemas de optimizacion y separacion sugiere que para estos problemas deberia existir alguna formulacion cuyo problema de separacion asociado pueda ser resuelto en tiempo polinomial y, mas aun, tal que el poliedro asociado admita una caracterizacion “elegante”, en terminos de desigualdades lineales. La busqueda de tales caracterizaciones es el objetivo principal del presente trabajo de tesis. El objetivo teorico es completar la contraparte poliedral de aquellos problemas de coloreo de grafos que se encuentren ya bien resueltos por medio de tecnicas combinatorias. El estudio de estos poliedros puede llevarnos a un mejor entendimiento de sus estructuras permitiendonos de esta forma encontrar nuevas familias de grafos para las cuales algunos problemas de coloreo tengan resoluci on polinomial, aportando asi nuevos resultados utiles en la practica. De este estudio surgen tambien nuevas familias de desigualdades validas que pueden incorporarse a algoritmos de planos de corte para contribuir asi a mejorar su performance en la practica. Con estos objetivos, en esta tesis estudiamos los poliedros asociados a cuatro formulaciones distintas para el problema clasico de coloreo: el modelo estandar, la formulacion por representantes, el orientation model y la formulacion por conjuntos independientes. Presentamos adaptaciones de algunas de estas formulaciones para distintas variantes de coloreo y en algunos casos mostramos que los problemas de optimizacion en los poliedros asociados son polinomialmente equivalentes al problema de optimizacion sobre el poliedro de coloreo clasico. 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 arboles, grafos block, split y co-interval, entre otras. Estudiamos tambien la relaci on 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 este) para un grafo asociado al grafo original. Estos resultados nos permiten obtener nuevas familias de desigualdades validas para Pcol basadas en desigualdades validas conocidas para STAB. Mas aun, a raiz de estos resultados hallamos descripciones completas de Pcol para algunas familias de grafos en las que se conoce una descripcion de STAB para el grafo asociado. Presentamos tambien un estudio poliedral clasico para el orientation model en el cual describimos algunas familias de desigualdades validas que definen facetas del poliedro asociado. Basados en la estructura de estas familias, presentamos el procedimiento de path lifting, que combina dos desigualdades validas genericas y un camino entre dos vertices particulares y genera una familia infinita de desigualdades validas. Mostramos que este procedimiento puede generar facetas del poliedro de coloreo asociado y damos condiciones suficientes para que esto ocurra.