Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
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 des...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/166456 |
| Aporte de: |
| Sumario: | 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. |
|---|