El Problema de la Mínima Violación Cromática: un estudio poliedral

BRAGA, MONICA; DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA; VARALDO, MARIA DEL CARMEN

Cordoba

Simposio; Simposio de Investigación Operativa de las JAIIO; 2017

SADIO

En este trabajo definimos una generalización del problema clásico de coloreo por vértices en un grafo, donde algunos pares de vértices pueden recibir el mismo color. Una arista del grafo es débil si conecta un par de tales vértices Buscamos un coloreo del grafo que minimice el número de aristas débiles que tienen sus extremos en el mismo color. Este problema es llamado el problema de la mínima violación cromática (MCVP). Presentamos una formulación entera para este problema y realizamos un primer estudio poliedral del politopo que surge de esta formulación. Damos una caracterización parcial de desigualdades que inducen facetas y mostramos como estan relacionadas distintas instancias del MCVP.Presentamos procedimientos generales de lifting que generan desigualdades válidas (bajo ciertas condiciones facetas) partiendo de desigualdades válidas genéricas. Exhibimos algunas familias de facetas que surgen a partir de estos procedimientos y otras que no se pueden generar con ellos. Finalmente, analizamos los casos límites de todas aristas débiles y su relación con el problema de la k-partition.