Registro:
| Documento: | Tesis de Grado |
| Título: | El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera |
| Autor: | Borghini, Fabrizio |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2015 |
| Fecha en portada: | 2015 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel |
| Director Asistente: | Zabala, Paula Lorena |
| Jurado: | Marenco, Javier Leonardo; Miranda Bront, Juan José |
| Idioma: | Español |
| Palabras clave: | ETIQUETADO TOTAL; COLOREO DE ARISTAS; PROGRAMACION LINEAL ENTERA; BRANCH AND CUT |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000653_Borghini.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000653_Borghini |
| Ubicación: | Dep.COM 000653 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Borghini, Fabrizio. (2015). El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini |
Resumen:
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.
Citación:
---------- APA ----------
Borghini, Fabrizio. (2015). El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini
---------- CHICAGO ----------
Borghini, Fabrizio. "El problema de coloreo de aristas por etiquetado total bajo un enfoque de programación lineal entera". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/seminario_nCOM000653_Borghini
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000653_Borghini.pdf
Distrubución geográfica
