Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafoss

Resumen

Dados un grafo G y un hipergrafo H sobre el mismo conjunto de vértices y dado un conjunto C de colores, el problema de coloreo de máximo impacto en hipergrafos solicita un C-coloreo de G que maximice la cantidad de hiperaristas de H cuyos vértices reciben todos el mismo color. Este problema surge en el contexto de la asignación de aulas a materias. El grafo G represnta los conflictos horarios entre sesiones, y las hiperaristas del grafo H representan conjuntos de sesiones de una misma materia, y es deseable que estas sesiones sean asignadas a una misma aula.

En este trabajo se inicia un estudio poliedral de una formulación de programación lineal entera para este problema. Se proponen dos modelos y se evalúa su performance en la práctica, concluyendo que uno de ellos tiene un mejor rendimiento. Se estudia la cápsula convexa de las soluciones factibles de este modelo, caracterizando su dimensión e identificando familias de desigualdades válidas. Se analizan las propiedades de estas familias, en particular presentando hipótesis adicionales que aseguran que estas desigualdades definen facetas del poliedro asociado.