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

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Singer, Jessica, Marenco, Javier Leonardo
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2023
Materias:
Ciencias Informáticas
coloreo
programación entera
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/166456
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-166456
record_format dspace
spelling I19-R120-10915-1664562024-05-28T20:10:07Z http://sedici.unlp.edu.ar/handle/10915/166456 Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos A polyhedral study of the maximum impact coloring problem in hypergraphs Singer, Jessica Marenco, Javier Leonardo 2023-09 2023 2024-05-28T13:05:15Z es Ciencias Informáticas coloreo programación entera 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. Sociedad Argentina de Informática e Investigación Operativa Objeto de conferencia Resumen http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 162-162
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
coloreo
programación entera
spellingShingle Ciencias Informáticas
coloreo
programación entera
Singer, Jessica
Marenco, Javier Leonardo
Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
topic_facet Ciencias Informáticas
coloreo
programación entera
description 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.
format Objeto de conferencia
Resumen
author Singer, Jessica
Marenco, Javier Leonardo
author_facet Singer, Jessica
Marenco, Javier Leonardo
author_sort Singer, Jessica
title Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
title_short Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
title_full Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
title_fullStr Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
title_full_unstemmed Un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
title_sort un estudio poliedral del problema de coloreo de máximo impacto en hipergrafos
publishDate 2023
url http://sedici.unlp.edu.ar/handle/10915/166456
work_keys_str_mv AT singerjessica unestudiopoliedraldelproblemadecoloreodemaximoimpactoenhipergrafos
AT marencojavierleonardo unestudiopoliedraldelproblemadecoloreodemaximoimpactoenhipergrafos
AT singerjessica apolyhedralstudyofthemaximumimpactcoloringprobleminhypergraphs
AT marencojavierleonardo apolyhedralstudyofthemaximumimpactcoloringprobleminhypergraphs
_version_ 1807223039692111872

Ejemplares similares