Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas

Para un problema de programación lineal entera, la técnica de cortes locales consiste en proyectar el poliedro asociado a la relajación lineal y una solución fraccionaria a un espacio de dimensión muy baja, encontrando ahí cortes que luego serán “elevados” al problema original; e iterar sobre este p...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Marenco, Javier, Martínez Viademonte, Javier, Mydlarz, Marcelo
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2016
Materias:
Ciencias Informáticas
branch-and-cut
programación lineal entera
MLSTP
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/58542
http://45jaiio.sadio.org.ar/sites/default/files/Sio-16.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-58542
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
branch-and-cut
programación lineal entera
MLSTP
spellingShingle Ciencias Informáticas
branch-and-cut
programación lineal entera
MLSTP
Marenco, Javier
Martínez Viademonte, Javier
Mydlarz, Marcelo
Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
topic_facet Ciencias Informáticas
branch-and-cut
programación lineal entera
MLSTP
description Para un problema de programación lineal entera, la técnica de cortes locales consiste en proyectar el poliedro asociado a la relajación lineal y una solución fraccionaria a un espacio de dimensión muy baja, encontrando ahí cortes que luego serán “elevados” al problema original; e iterar sobre este procedimiento. La intención es obtener cortes que puedan ser aplicados en el contexto de un algoritmo de branch-and-cut sin recurrir a caracterizaciones previas de familias de desigualdades válidas, aprovechando fuertemente la reducción en el tamaño del problema y eligiendo una variedad de proyecciones en caso de ser conveniente. En este trabajo estudiamos el problema de encontrar un árbol generador con máxima cantidad de hojas (MLSTP) sobre un grafo conexo, un problema de interés para la industria de las telecomunicaciones. Se presentan resultados y desafíos de abordar el problema con la técnica de cortes locales, y algunas vinculaciones con familias conocidas de desigualdades válidas para el problema.
format Objeto de conferencia
Resumen
author Marenco, Javier
Martínez Viademonte, Javier
Mydlarz, Marcelo
author_facet Marenco, Javier
Martínez Viademonte, Javier
Mydlarz, Marcelo
author_sort Marenco, Javier
title Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_short Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_full Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_fullStr Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_full_unstemmed Resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_sort resultados con cortes locales para el problema de árbol generador con máxima cantidad de hojas
publishDate 2016
url http://sedici.unlp.edu.ar/handle/10915/58542
http://45jaiio.sadio.org.ar/sites/default/files/Sio-16.pdf
work_keys_str_mv AT marencojavier resultadosconcorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
AT martinezviademontejavier resultadosconcorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
AT mydlarzmarcelo resultadosconcorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
bdutipo_str Repositorios
_version_ 1764820477999579139

Ejemplares similares