La Optimización Combinatoria, que permite modelar una gran variedad de problemas provenientes de las aplicaciones, tiene en la Programación Lineal Entera/Mixta (PLE/M) una de sus grandes estrategias de resolución. A partir de una formulación inicial, se busca obtener aproximaciones poliedrales sucesivas que contengan a las soluciones del problema. Sin embargo, el número de pasos puede ser muy grande y no se conoce una implementación algorítmica eficiente en general.
Una clase de problemas combinatorios donde este abordaje poliedral va creciendo en importancia es la de los problemas de coloreo de grafos. El proyecto se basa en el estudio teórico-práctico de dos variantes del problema estándar de coloreo (Temas 1 y 2) y en la modelización y resolución como coloreo de un grafo del problema de asignación de aulas en una institución educativa (Tema 3).
TEMA 1: Problema de violación cromática mínima.
Dado un grafo G = (V,E), un subconjunto de aristas F “violables” y una cantidad c de colores, el problema consiste en encontrar un coloreo del grafo G_F = (V,E- F) con c colores que minimice la cantidad de aristas de F cuyos extremos reciben el mismo color. Si F es vacío, es el problema estándar de coloreo. Este problema es muy interesante para las aplicaciones prácticas donde es habitual permitir leves violaciones a las restricciones de coloreo si no es posible encontrar uno con la cantidad de colores especificada. Nos proponemos abordarlo desde el punto de vista teórico (abordaje poliedral) y desde el punto de vista práctico (implementación de algoritmos).
TEMA 2: Problema del coloreo por vértices con adyacencias mínimas.
El problema de coloreo de vértices de un grafo de manera de minimizar la cantidad de vértices vecinos que reciban colores adyacentes (consecutivos de acuerdo a un orden establecido), proviene de la asignación de frecuencias en redes móviles.
Nos proponemos profundizar su estudio poliedral (iniciado en [11] al adaptar una de las formulaciones del problema de coloreo estándar a esta variante) por un lado, hallando nuevas familias de desigualdades válidas y condiciones para que las mismas describan el poliedro en estudio, y por otro, estudiando nuevas formulaciones para el mismo.
TEMA 3: Aplicación a la distribución de aulas.
Los problemas de asignación de aulas surgen naturalmente en el contexto de instituciones educativas, cuando se debe asignar un aula a cada curso sin incurrir en superposiciones horarias. Consideramos el problema particular que surge en instituciones que cuentan con más de una sede o más de un edificio dentro de un predio extenso. Proponemos estudiar modelos PLE para este problema y sus variantes, analizando los tamaños de instancias resolubles. Para aquel que obtenga los mejores resultados computacionales, analizaremos su poliedro asociado para obtener desigualdades válidas que permitan acelerar su resolución. Finalmente, estudiaremos la facetitud de las desigualdades halladas, para tener una medida teórica de su calidad.
