Problemas en coloreos de aristas con vértices adyacentes distinguibles

Mostrar todas las versiones(3)

En el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe...

Descripción completa

Detalles Bibliográficos
Autor principal: Curcio, Brian Luis
Otros Autores: Zabala, Paula Lorena
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2021
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7050_Curcio
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n7050_Curcio_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n7050_Curcio_oai
record_format dspace
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
description En el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe tener distinto color, y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores asignados en un coloreo de aristas que cumpla estas restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de grafos, que resultan una herramienta abstracta muy útil y versátil para modelar situaciones de la vida cotidiana que se quieren formalizar y resolver mediante algoritmos. Algunas variantes del problema de etiquetado de grafos han sido abordadas con éxito con técnicas de programación lineal entera basadas en la caracterización poliedral del conjunto de soluciones factibles. Bajo este enfoque, en esta tesis nos proponemos desarrollar un algoritmo tipo Branch and Cut para resolver el problema. Además, aprovechando el análisis realizado, también hacemos una propuesta algorítmica para resolver el problema que busca minimizar la cantidad de colores utilizados en el coloreo. Adicionalmente, se exploró la opción de utilizar técnicas heurísticas para resolver el problema. Las heurísticas permiten conocer asignaciones de colores factibles del problema pero, en general, no pueden determinar si son óptimas o cuan cerca están de la solución del problema. Desarrollamos tres técnicas distintas para resolver el problema: un algoritmo goloso, un algoritmo de programación por restricciones, y un algoritmo de generación de columnas. Para el desarrollo del algoritmo tipo Branch and Cut, propusimos dos modelos de programación lineal entera que evaluamos empíricamente para elegir el más prometedor, sobre el cual se realizó un estudio poliedral en profundidad. Caracterizamos la dimensión del poliedro asociado y demostramos que tres familias de desigualdades válidas definen facetas. El objetivo de realizar el estudio poliedral es entender mejor el espacio de soluciones del modelo para conseguir formulaciones más ajustadas que mejoren la performance del algoritmo. Las desigualdades estudiadas son incorporadas como cortes al modelo, para las cuales se desarrollaron algoritmos de separación que permiten agregarlas a demanda. Además, se consideraron heurística inicial, preprocesamiento y estrategias particulares de generación del árbol de búsqueda. Los resultados muestran que el algoritmo desarrollado permite resolver instancias que no son posibles de abordar utilizando las herramientas de resolución generales. Haber realizado el estudio poliedral y agregar las facetas como planos de corte resulta ser un factor determinante para afrontar instancias del problema mucho más desafiantes.
author2 Zabala, Paula Lorena
author_facet Zabala, Paula Lorena
Curcio, Brian Luis
format Tesis doctoral
Tesis doctoral
publishedVersion
author Curcio, Brian Luis
spellingShingle Curcio, Brian Luis
Problemas en coloreos de aristas con vértices adyacentes distinguibles
author_sort Curcio, Brian Luis
title Problemas en coloreos de aristas con vértices adyacentes distinguibles
title_short Problemas en coloreos de aristas con vértices adyacentes distinguibles
title_full Problemas en coloreos de aristas con vértices adyacentes distinguibles
title_fullStr Problemas en coloreos de aristas con vértices adyacentes distinguibles
title_full_unstemmed Problemas en coloreos de aristas con vértices adyacentes distinguibles
title_sort problemas en coloreos de aristas con vértices adyacentes distinguibles
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2021
url https://hdl.handle.net/20.500.12110/tesis_n7050_Curcio
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n7050_Curcio_oai
work_keys_str_mv AT curciobrianluis problemasencoloreosdearistasconverticesadyacentesdistinguibles
AT curciobrianluis problemsonvertexdistinguishingedgecolorings
_version_ 1824355573466923008
spelling I28-R145-tesis_n7050_Curcio_oai2024-09-02 Zabala, Paula Lorena Curcio, Brian Luis 2021-12-27 En el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe tener distinto color, y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores asignados en un coloreo de aristas que cumpla estas restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de grafos, que resultan una herramienta abstracta muy útil y versátil para modelar situaciones de la vida cotidiana que se quieren formalizar y resolver mediante algoritmos. Algunas variantes del problema de etiquetado de grafos han sido abordadas con éxito con técnicas de programación lineal entera basadas en la caracterización poliedral del conjunto de soluciones factibles. Bajo este enfoque, en esta tesis nos proponemos desarrollar un algoritmo tipo Branch and Cut para resolver el problema. Además, aprovechando el análisis realizado, también hacemos una propuesta algorítmica para resolver el problema que busca minimizar la cantidad de colores utilizados en el coloreo. Adicionalmente, se exploró la opción de utilizar técnicas heurísticas para resolver el problema. Las heurísticas permiten conocer asignaciones de colores factibles del problema pero, en general, no pueden determinar si son óptimas o cuan cerca están de la solución del problema. Desarrollamos tres técnicas distintas para resolver el problema: un algoritmo goloso, un algoritmo de programación por restricciones, y un algoritmo de generación de columnas. Para el desarrollo del algoritmo tipo Branch and Cut, propusimos dos modelos de programación lineal entera que evaluamos empíricamente para elegir el más prometedor, sobre el cual se realizó un estudio poliedral en profundidad. Caracterizamos la dimensión del poliedro asociado y demostramos que tres familias de desigualdades válidas definen facetas. El objetivo de realizar el estudio poliedral es entender mejor el espacio de soluciones del modelo para conseguir formulaciones más ajustadas que mejoren la performance del algoritmo. Las desigualdades estudiadas son incorporadas como cortes al modelo, para las cuales se desarrollaron algoritmos de separación que permiten agregarlas a demanda. Además, se consideraron heurística inicial, preprocesamiento y estrategias particulares de generación del árbol de búsqueda. Los resultados muestran que el algoritmo desarrollado permite resolver instancias que no son posibles de abordar utilizando las herramientas de resolución generales. Haber realizado el estudio poliedral y agregar las facetas como planos de corte resulta ser un factor determinante para afrontar instancias del problema mucho más desafiantes. In this thesis we analyze the adjacent vertex distinguishing sum edge coloring problem. This problem consists in finding an assignment of colors to the edges of a graph with the following constraints: every pair of adjacent edges must have a different color, and every pair of adjacent vertices must not have the same set of colors assigned to the edges incident to each. The goal is to minimize the sum of the colors in an edge coloring that satisfies these constraints. This problem is a special case of a large family of problems known as graph labeling, which are a widely used and very popular set of tools to build abstract models for problems that come up in everyday life. Some variants of graph labeling problem have been successfully addressed with mixed integer linear programming (MIP) techniques based on a polyhedral characterization of the set of feasible solutions. We use this approach to develop a branch and cut algorithm to solve the problem. Furthermore, taking advantage of the analysis, we also propose an algorithm to solve the problem that minimizes the number of colors used for an adjacent vertex distinguishing edge coloring. Additionally, we explored using heuristic techniques to solve the problem. These heuristics allow to obtain feasible coloring assignments for the problem but, in general, can not determine if they are optimal or even how far they are from the solution to the problem. We use three different approaches: a greedy algorithm, a constraint programming model and a column generation algorithm. To develop the branch and cut algorithm we propose two MIP models. We evaluate these models to choose the most promising one and continue with a thorough polyhedral study. We characterized the dimension of the associated polyhedron and proved that three families of valid inequalities result facet-inducing. The aim of the polyhedral study is to understand the set of feasible solutions in the model to obtain a more compact formulation in hope of improving the algorithm's performance. These inequalities are added as cutting planes in the model, we developed exact and heuristic separation algorithms to add them on demand. Moreover, we considered the use of initial heuristics, preprocessing and particular branching strategies. The results show that the algorithm developed allows us to solve instances that were unsolvable using general purpose solvers. Our polyhedral study and the addition of facets as cutting planes proved to be a crucial factor to solve the most challenging instances. Fil: Curcio, Brian Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n7050_Curcio 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 Problemas en coloreos de aristas con vértices adyacentes distinguibles Problems on vertex distinguishing edge colorings info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n7050_Curcio_oai

Ejemplares similares