Evaluación computacional de los 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 la cápsula convexa de las soluciones factibles y una solución fraccionaria de la relajación lineal a un espacio de dimensión muy baja, encontrando ahí cortes que luego serán “elevados” al problema orig...

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: 2019
Materias:
Ciencias Informáticas
Cortes locales
Branch-and-cut
Programación lineal entera
MLSTP
Lifting secuencial
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/89665
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-89665
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
Cortes locales
Branch-and-cut
Programación lineal entera
MLSTP
Lifting secuencial
spellingShingle Ciencias Informáticas
Cortes locales
Branch-and-cut
Programación lineal entera
MLSTP
Lifting secuencial
Marenco, Javier
Martínez Viademonte, Javier
Mydlarz, Marcelo
Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
topic_facet Ciencias Informáticas
Cortes locales
Branch-and-cut
Programación lineal entera
MLSTP
Lifting secuencial
description Para un problema de programación lineal entera, la técnica de cortes locales consiste en proyectar la cápsula convexa de las soluciones factibles y una solución fraccionaria de la relajación lineal 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 presentán resultados y un análisis, con foco en el desempeño computacional, productos de abordar el problema con la técnica de cortes locales.
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 Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_short Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_full Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_fullStr Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_full_unstemmed Evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
title_sort evaluación computacional de los cortes locales para el problema de árbol generador con máxima cantidad de hojas
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/89665
work_keys_str_mv AT marencojavier evaluacioncomputacionaldeloscorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
AT martinezviademontejavier evaluacioncomputacionaldeloscorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
AT mydlarzmarcelo evaluacioncomputacionaldeloscorteslocalesparaelproblemadearbolgeneradorconmaximacantidaddehojas
bdutipo_str Repositorios
_version_ 1764820490157817858

Ejemplares similares