Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos

Mostrar todas las versiones(2)

Los problemas de coloreo de grafos constituyen una familia de problemas de una gran relevancia tanto teórica como práctica. Todos ellos son variaciones del problema del coloreo clásico, cuyo estudio se inició en el Siglo XIX. El origen de estas variaciones radica en las restricciones adicionales que...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Severin, Daniel Esteban
Otros Autores: Méndez-Díaz, Isabel
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2012
Materias:
BRANCH-AND-CUT
COLOREO EQUITATIVO DE GRAFOS
PROGRAMACION LINEAL ENTERA
POLIEDROS
PLANOS DE CORTE
EQUITABLE GRAPH COLORING
INTEGER LINEAR PROGRAMMING
POLYHEDRA
CUTTING PLANE
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5080_Severin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n5080_Severin
record_format dspace
spelling tesis:tesis_n5080_Severin2023-10-02T20:04:06Z Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos A polyhedral study and a Branch-and-Cut algorithm for the equitable graph coloring problem Severin, Daniel Esteban Méndez-Díaz, Isabel Nasini, Graciela L. BRANCH-AND-CUT COLOREO EQUITATIVO DE GRAFOS PROGRAMACION LINEAL ENTERA POLIEDROS PLANOS DE CORTE BRANCH-AND-CUT EQUITABLE GRAPH COLORING INTEGER LINEAR PROGRAMMING POLYHEDRA CUTTING PLANE Los problemas de coloreo de grafos constituyen una familia de problemas de una gran relevancia tanto teórica como práctica. Todos ellos son variaciones del problema del coloreo clásico, cuyo estudio se inició en el Siglo XIX. El origen de estas variaciones radica en las restricciones adicionales que imponen las aplicaciones a problemas de la vida real. En esta tesis abordamos en particular el Problema de Coloreo Equitativo en Grafos. Como muchos problemas de Optimización Combinatoria, el Problema de Coloreo Equitativo es un problema NP-difícil. Los algoritmos Branch-and-Cut basados en el estudio poliedral de una formulación del problema como programa lineal entero, son la herramienta más efectiva que se conoce para la resolución exacta de problemas NP-difíciles. En esta tesis se propone un modelo de programación lineal entera para el Problema del Coloreo Equitativo y se estudia el poliedro asociado. Se derivan varias familias de desigualdades validas y se prueba que siempre definen caras de alta dimensión, lo cual es un buen indicador para la utilización de las mismas como planos de corte. Finalmente, se desarrolla e implementa un algoritmo Branch-and-Cut para el Problema de Coloreo Equitativo que resulta altamente competitivo con los algoritmos exactos conocidos. The graph coloring problems constitute a family of problems of great theoretical and practical relevance. All of them are variations of the classical coloring problem, whose study began in the nineteenth century. The origin of these variations arises from the additional restrictions imposed by applications to real life problems. In particular, this thesis deals with the Equitable Graph Coloring Problem. Like many combinatorial optimization problems, the Equitable Coloring Problem is NP-hard. It is known that Branch-and-Cut algorithms based on the polyhedral study of a formulation of the problem as an integer linear program, are the most effective tool for solving NP-hard problems. This thesis proposes a linear integer programming model for the Equitable Coloring Problem and studies the polytope associated to that model. Several families of valid inequalities that define faces of high dimension are derived in order to use them later as cutting planes. Finally, a Branch-and-Cut algorithm for the Equitable Coloring Problem that is highly competitive against known exact algorithms is developed. Fil: Severin, Daniel Esteban. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2012 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n5080_Severin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic BRANCH-AND-CUT
COLOREO EQUITATIVO DE GRAFOS
PROGRAMACION LINEAL ENTERA
POLIEDROS
PLANOS DE CORTE
BRANCH-AND-CUT
EQUITABLE GRAPH COLORING
INTEGER LINEAR PROGRAMMING
POLYHEDRA
CUTTING PLANE
spellingShingle BRANCH-AND-CUT
COLOREO EQUITATIVO DE GRAFOS
PROGRAMACION LINEAL ENTERA
POLIEDROS
PLANOS DE CORTE
BRANCH-AND-CUT
EQUITABLE GRAPH COLORING
INTEGER LINEAR PROGRAMMING
POLYHEDRA
CUTTING PLANE
Severin, Daniel Esteban
Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
topic_facet BRANCH-AND-CUT
COLOREO EQUITATIVO DE GRAFOS
PROGRAMACION LINEAL ENTERA
POLIEDROS
PLANOS DE CORTE
BRANCH-AND-CUT
EQUITABLE GRAPH COLORING
INTEGER LINEAR PROGRAMMING
POLYHEDRA
CUTTING PLANE
description Los problemas de coloreo de grafos constituyen una familia de problemas de una gran relevancia tanto teórica como práctica. Todos ellos son variaciones del problema del coloreo clásico, cuyo estudio se inició en el Siglo XIX. El origen de estas variaciones radica en las restricciones adicionales que imponen las aplicaciones a problemas de la vida real. En esta tesis abordamos en particular el Problema de Coloreo Equitativo en Grafos. Como muchos problemas de Optimización Combinatoria, el Problema de Coloreo Equitativo es un problema NP-difícil. Los algoritmos Branch-and-Cut basados en el estudio poliedral de una formulación del problema como programa lineal entero, son la herramienta más efectiva que se conoce para la resolución exacta de problemas NP-difíciles. En esta tesis se propone un modelo de programación lineal entera para el Problema del Coloreo Equitativo y se estudia el poliedro asociado. Se derivan varias familias de desigualdades validas y se prueba que siempre definen caras de alta dimensión, lo cual es un buen indicador para la utilización de las mismas como planos de corte. Finalmente, se desarrolla e implementa un algoritmo Branch-and-Cut para el Problema de Coloreo Equitativo que resulta altamente competitivo con los algoritmos exactos conocidos.
author2 Méndez-Díaz, Isabel
author_facet Méndez-Díaz, Isabel
Severin, Daniel Esteban
format Tesis doctoral
Tesis doctoral
publishedVersion
author Severin, Daniel Esteban
author_sort Severin, Daniel Esteban
title Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
title_short Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
title_full Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
title_fullStr Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
title_full_unstemmed Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
title_sort estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2012
url https://hdl.handle.net/20.500.12110/tesis_n5080_Severin
work_keys_str_mv AT severindanielesteban estudiopoliedralyalgoritmobranchandcutparaelproblemadecoloreoequitativoengrafos
AT severindanielesteban apolyhedralstudyandabranchandcutalgorithmfortheequitablegraphcoloringproblem
_version_ 1782023122241716224

Ejemplares similares