Estudio poliedral del problema de coloreo acíclico
Autor: Braga, Mónica
Resumen
Un coloreo de un grafo es una asignación de colores a sus vértices de modo tal que todo par de vértices adyacentes recibe colores distintos. Un coloreo acíclico de un grafo es un coloreo tal que ningún ciclo del grafo recibe exactamente dos colores, y el número cromático acíclico XA(G)de un grafo G se define como el número mínimo de colores necesarios para garantizar la existencia de un coloreo acíclico de G. Dado un grafo G, el problema de coloreo acíclico consiste en hallar un coloreo acíclico de G con XA(G) colores. Este problema surge en el contexto de la implementación de algoritmos eficientes para el cálculo de matrices Hessianas poco densas y simétricas a través de métodos de sustitución. Dado un grafo G y un entero k, el problema de determinar si XA(G) <= k es un problema NPcompleto, con lo cual no se conocen algoritmos eficientes (es decir, polinomiales en el tamaño de G) para este problema. En particular, el problema de determinar si XA(G) <= 3 es NP-completo.
Una técnica que suele ser exitosa para la resolución computacional de problemas de optimización combinatoria es el planteo de algoritmos basados en planos de corte, sobre la base de una formulación del problema como un modelo de programación lineal entera. Este enfoque involucra el estudio de la cápsula convexa de las soluciones factibles del modelo planteado, buscando familias de desigualdades válidas que puedan ser incorporadas en un algoritmo de este tipo. Dado que este enfoque resultó útil para muchos otros problemas, en esta tesis se comienza este estudio para el problema de coloreo acíclico. En esta tesis se introduce un modelo de programación lineal entera para el problema de coloreo acíclico y se estudian sus propiedades. Se analiza la dimensión de la cápsula convexa de las soluciones factibles y, sobre esta base, se estudian desigualdades válidas y se analizan sus propiedades. Se presentan familias de desigualdades válidas basadas en ciclos y cliques del grafo, y se prueba bajo qué condiciones estas desigualdades definen facetas del poliedro cápsula convexa asociado con la formulación. Se muestra que todas las desigualdades
presentadas en este trabajo definen facetas bajo condiciones generales. Se estudia además el rango disyuntivo de las familias de desigualdades presentadas en este trabajo, asociado al operador BCC definido por Balas, Ceria y Cornuéjols. Se propone en esta tesis un concepto complementario al de rango disyuntivo, llamado anti-rango disyuntivo de una desigualdad válida. Este parámetro es de interés como medida teórica de la calidad de la desigualdad, y se estudian los anti-rangos disyuntivos de las desigualdades presentadas en este trabajo.