El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera

Mostrar todas las versiones(2)

En este trabajo se aborda bajo un enfoque de programación lineal entera el problema de coloreo de aristas por etiquetado total. Este concepto fue introducido por S. Brandt, D. Rautenbach y M. Stiebitz en el año 2007. A lo largo del trabajo se realizan formulaciones de programación lineal entera para...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Borghini, Fabrizio
Otros Autores: Méndez Díaz, Isabel
Formato: Tesis de grado publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2015
Materias:
ETIQUETADO TOTAL
COLOREO DE ARISTAS
PROGRAMACION LINEAL ENTERA
BRANCH AND CUT
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000653_Borghini_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-seminario_nCOM000653_Borghini_oai
record_format dspace
spelling I28-R145-seminario_nCOM000653_Borghini_oai2025-08-20 Méndez Díaz, Isabel Zabala, Paula Lorena Borghini, Fabrizio 2015 En este trabajo se aborda bajo un enfoque de programación lineal entera el problema de coloreo de aristas por etiquetado total. Este concepto fue introducido por S. Brandt, D. Rautenbach y M. Stiebitz en el año 2007. A lo largo del trabajo se realizan formulaciones de programación lineal entera para modelar el problema y se compara el rendimiento de los modelos mediante distintos criterios. Además, para cada modelo desarrollado, se realiza un estudio poliedral con el propósito de encontrar familias de desigualdades válidas a partir de las cuáles desarrollar un algoritmo de Branch & Cut. Con el objetivo de mejorar la eficiencia en la resolución de instancias, se desarrollan distintas heurísticas iniciales que permiten contar con una solución factible de la cuál partir para optimizar el problema. También se implementa una heurística primaria para cada modelo con la intención de encontrar soluciones enteras cercanas al óptimo. Por último, se presentan los resultados obtenidos sobre diversas instancias de grafos para evaluar la performance de los modelos implementados. Fil: Borghini, Fabrizio. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar ETIQUETADO TOTAL COLOREO DE ARISTAS PROGRAMACION LINEAL ENTERA BRANCH AND CUT El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000653_Borghini_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
topic ETIQUETADO TOTAL
COLOREO DE ARISTAS
PROGRAMACION LINEAL ENTERA
BRANCH AND CUT
spellingShingle ETIQUETADO TOTAL
COLOREO DE ARISTAS
PROGRAMACION LINEAL ENTERA
BRANCH AND CUT
Borghini, Fabrizio
El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
topic_facet ETIQUETADO TOTAL
COLOREO DE ARISTAS
PROGRAMACION LINEAL ENTERA
BRANCH AND CUT
description En este trabajo se aborda bajo un enfoque de programación lineal entera el problema de coloreo de aristas por etiquetado total. Este concepto fue introducido por S. Brandt, D. Rautenbach y M. Stiebitz en el año 2007. A lo largo del trabajo se realizan formulaciones de programación lineal entera para modelar el problema y se compara el rendimiento de los modelos mediante distintos criterios. Además, para cada modelo desarrollado, se realiza un estudio poliedral con el propósito de encontrar familias de desigualdades válidas a partir de las cuáles desarrollar un algoritmo de Branch & Cut. Con el objetivo de mejorar la eficiencia en la resolución de instancias, se desarrollan distintas heurísticas iniciales que permiten contar con una solución factible de la cuál partir para optimizar el problema. También se implementa una heurística primaria para cada modelo con la intención de encontrar soluciones enteras cercanas al óptimo. Por último, se presentan los resultados obtenidos sobre diversas instancias de grafos para evaluar la performance de los modelos implementados.
author2 Méndez Díaz, Isabel
author_facet Méndez Díaz, Isabel
Borghini, Fabrizio
format Tesis de grado
Tesis de grado
publishedVersion
author Borghini, Fabrizio
author_sort Borghini, Fabrizio
title El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
title_short El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
title_full El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
title_fullStr El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
title_full_unstemmed El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
title_sort el problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2015
url https://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000653_Borghini_oai
work_keys_str_mv AT borghinifabrizio elproblemadecoloreodearistasporetiquetadototalbajounenfoquedeprogramacionlinealentera
_version_ 1843127019942969344

Ejemplares similares