EL PROBLEMA DE SEPARACIÓN DE FACETAS DEL POLIEDRO DE MÍNIMA VIOLACIÓN CROMÁTICA

DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA

Congreso; VirtUMA 2020; 2020

Unión Matemática Argentina

En [1] consideramos una generalizaci´on del problema cl´asico de coloreode v´ertices (VCP), llamado el problema de la m´ınima violaci´on crom´atica(MCVP). Dado un grafo G = (V; E), un conjunto de colores C y un subconjunto de aristas d´ebiles F ⊆ E, se busca un jCj-coloreo de G0 = (V; E n F)que minimice el n´umero de aristas de F con ambos extremos en la mismaclase de color.En [1] definimos el poliedro de m´ınima violaci´on crom´atica como lac´apsula convexa de las soluciones factibles del MCVP. Para ello nos basamosen la formulaci´on est´andar del VCP dada en [2]. Completando el estudio poliedral de MCVP, se encontraron distintas familias de desigualdades v´alidasde tama~no exponencial asociadas a estructuras particulares presentes en elgrafo, como cliques y agujeros impares, y condiciones suficientes para quelas mismas definan facetas.En este trabajo consideramos el problema de separaci´on de estas familiasde desigualdades. La familia m´as simple a ser considerada es la de las llamadas desigualdades de weak-clique, que generalizan a las desigualdades cliquepara el problema de coloreo est´andar y fueron obtenidas por aplicaci´on deun procedimiento de lifting definido en [1]. Tambi´en consideramos las familias de desigualdades multicolor-clique y multicolor-combinatorial clique,halladas en el mismo trabajo. Al estar todas ellas asociadas a la presencia decliques en el grafo, es necesario considerar distintas heur´ısticas para abordarla separaci´on de las mismas.Adem´as, consideramos una familia de desigualdades v´alidas asociadas aagujeros impares en el grafo y, en las condiciones en que definen facetas,probamos que son separables en tiempo polinomial.Actualmente estamos trabajando en el desarrollo de un procedimiento destrength-and-lift que consiste en fortalecer algunas aristas d´ebiles, buscar uncorte apropiado en esta nueva instancia que elimine una soluci´on fraccionariaen ella y luego aplicar el procedimiento de lifting mencionado para obtener,posiblemente, un nuevo corte en la instancia original.Referencias[1] Braga M., Delle Donne D., Escalante M., Marenco J., Ugarte M. E.,Varaldo M. C., The minimum chromatic violation problem: a polyhedralapproach. Discrete Applied Mathematics 281 (2020) 69-80.[2] Delle Donne D., Marenco J., Polyhedral studies of vertex coloring problems: The standard formulation. Discrete Optimization 21 (2016) 1-13.