Título: Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
Director: Javier Marenco
Jurados: Dra. Isabel Méndez Díaz y Dra. Paula Zabala

Resumen:

Dados un grafo G = (V, E), un hipergrafo H = (V, EH) sobre el mismo conjunto de vértices y un conjunto C de colores, el problema de coloreo de m+aximo impacto en hipergrafos consiste en hallar un coloreo factible de G que
maximice la cantidad de hiperaristas de H que se asignan al mismo color.

Este problema surge en el contexto de asignación de aulas a clases, donde V es el conjunto de clases semanales de una institución educativa, C son las aulas de la misma, y las aristas del grafo H conectan a las clases de una misma asignatura. En este sentido, una particularidad que intentaremos modelar será la preferencia por asignar a todas las clases de una misma asignatura, una misma aula. Sin embargo, habrá que tomar en cuenta los casos donde esto no será posible por superposiciones horarias.

Para este problema, analizamos dos modelos de programación lineal entera, concluyendo que uno de ellos muestra una ejecución más veloz en la práctica. Utilizando el modelo ganador, hacemos un estudio del poliedro inducido por las soluciones factibles de éste, calculando su dimensión y buscando desigualdades válidas y facetas.