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

Abstract

Los problemas de asignación de aulas tienen muchas características en función de las necesidades y restricciones de cada institución (capacidad de las aulas, distintos tipos de aula, preferencias de los docentes, etc.). El problema de coloreo de máximo impacto modela una de estas características deseables, a saber, la necesidad de que todas las sesiones de una misma materia se lleven a cabo en la 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.