Estudio poliedral del problema de coloreo acíclico

Mostrar todas las versiones(2)

Un coloreo de un grafo es una asignación de colores a sus vértices de modo tal que todo par de vértices adyacentes recibe colores distintos. Un coloreo acíclico de un grafo es un coloreo tal que ningún ciclo del grafo recibe exactamente dos colores, y el número cromático acíclico XA(G)de un grafo G...

Descripción completa

Detalles Bibliográficos
Autor principal: Braga, Mónica Andrea
Otros Autores: Marenco, Javier
Formato: Tesis doctoral acceptedVersion
Lenguaje:Español
Publicado: Universidad Nacional de General Sarmiento 2019
Materias:
CONCEPTOS MATEMATICOS
MODELOS MATEMATICOS
PROGRAMACION
COMPUTACION
Acceso en línea:http://repositorio.ungs.edu.ar/handle/UNGS/256
Aporte de:
Repositorio Institucional Digital de Acceso Abierto (UNGS) de Universidad Nacional de General Sarmiento
id I71-R177-UNGS-256
record_format dspace
spelling I71-R177-UNGS-2562023-06-21T12:55:31Z Estudio poliedral del problema de coloreo acíclico Braga, Mónica Andrea Marenco, Javier CONCEPTOS MATEMATICOS MODELOS MATEMATICOS PROGRAMACION COMPUTACION Un coloreo de un grafo es una asignación de colores a sus vértices de modo tal que todo par de vértices adyacentes recibe colores distintos. Un coloreo acíclico de un grafo es un coloreo tal que ningún ciclo del grafo recibe exactamente dos colores, y el número cromático acíclico XA(G)de un grafo G se define como el número mínimo de colores necesarios para garantizar la existencia de un coloreo acíclico de G. Dado un grafo G, el problema de coloreo acíclico consiste en hallar un coloreo acíclico de G con XA(G) colores. Este problema surge en el contexto de la implementación de algoritmos eficientes para el cálculo de matrices Hessianas poco densas y simétricas a través de métodos de sustitución. Dado un grafo G y un entero k, el problema de determinar si XA(G) <= k es un problema NPcompleto, con lo cual no se conocen algoritmos eficientes (es decir, polinomiales en el tamaño de G) para este problema. En particular, el problema de determinar si XA(G) <= 3 es NP-completo.Una técnica que suele ser exitosa para la resolución computacional de problemas de optimización combinatoria es el planteo de algoritmos basados en planos de corte, sobre la base de una formulación del problema como un modelo de programación lineal entera. Este enfoque involucra el estudio de la cápsula convexa de las soluciones factibles del modelo planteado, buscando familias de desigualdades válidas que puedan ser incorporadas en un algoritmo de este tipo. Dado que este enfoque resultó útil para muchos otros problemas, en esta tesis se comienza este estudio para el problema de coloreo acíclico.En esta tesis se introduce un modelo de programación lineal entera para el problema de coloreo acíclico y se estudian sus propiedades. Se analiza la dimensión de la cápsula convexa de las soluciones factibles y, sobre esta base, se estudian desigualdades válidas y se analizan sus propiedades. Se presentan familias de desigualdades válidas basadas en ciclos y cliques del grafo, y se prueba bajo qué condiciones estas desigualdades definen facetas del poliedro cápsula convexa asociado con la formulación. Se muestra que todas las desigualdades presentadas en este trabajo definen facetas bajo condiciones generales.Se estudia además el rango disyuntivo de las familias de desigualdades presentadas en este trabajo, asociado al operador BCC definido por Balas, Ceria y Cornuéjols. Se propone en esta tesis un concepto complementario al de rango disyuntivo, llamado anti-rango disyuntivo de una desigualdad válida. Este parámetro es de interés como medida teórica de la calidad de la desigualdad, y se estudian los anti-rangos disyuntivos de las desigualdades presentadas en este trabajo. Fil: Braga, Mónica Andrea. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. 2019-06-03T20:10:13Z 2019-06-03T20:10:13Z 2015 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/acceptedVersion http://repositorio.ungs.edu.ar/handle/UNGS/256 spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf 99 p. application/pdf Universidad Nacional de General Sarmiento
institution Universidad Nacional de General Sarmiento
institution_str I-71
repository_str R-177
collection Repositorio Institucional Digital de Acceso Abierto (UNGS)
language Español
orig_language_str_mv spa
topic CONCEPTOS MATEMATICOS
MODELOS MATEMATICOS
PROGRAMACION
COMPUTACION
spellingShingle CONCEPTOS MATEMATICOS
MODELOS MATEMATICOS
PROGRAMACION
COMPUTACION
Braga, Mónica Andrea
Estudio poliedral del problema de coloreo acíclico
topic_facet CONCEPTOS MATEMATICOS
MODELOS MATEMATICOS
PROGRAMACION
COMPUTACION
description Un coloreo de un grafo es una asignación de colores a sus vértices de modo tal que todo par de vértices adyacentes recibe colores distintos. Un coloreo acíclico de un grafo es un coloreo tal que ningún ciclo del grafo recibe exactamente dos colores, y el número cromático acíclico XA(G)de un grafo G se define como el número mínimo de colores necesarios para garantizar la existencia de un coloreo acíclico de G. Dado un grafo G, el problema de coloreo acíclico consiste en hallar un coloreo acíclico de G con XA(G) colores. Este problema surge en el contexto de la implementación de algoritmos eficientes para el cálculo de matrices Hessianas poco densas y simétricas a través de métodos de sustitución. Dado un grafo G y un entero k, el problema de determinar si XA(G) <= k es un problema NPcompleto, con lo cual no se conocen algoritmos eficientes (es decir, polinomiales en el tamaño de G) para este problema. En particular, el problema de determinar si XA(G) <= 3 es NP-completo.Una técnica que suele ser exitosa para la resolución computacional de problemas de optimización combinatoria es el planteo de algoritmos basados en planos de corte, sobre la base de una formulación del problema como un modelo de programación lineal entera. Este enfoque involucra el estudio de la cápsula convexa de las soluciones factibles del modelo planteado, buscando familias de desigualdades válidas que puedan ser incorporadas en un algoritmo de este tipo. Dado que este enfoque resultó útil para muchos otros problemas, en esta tesis se comienza este estudio para el problema de coloreo acíclico.En esta tesis se introduce un modelo de programación lineal entera para el problema de coloreo acíclico y se estudian sus propiedades. Se analiza la dimensión de la cápsula convexa de las soluciones factibles y, sobre esta base, se estudian desigualdades válidas y se analizan sus propiedades. Se presentan familias de desigualdades válidas basadas en ciclos y cliques del grafo, y se prueba bajo qué condiciones estas desigualdades definen facetas del poliedro cápsula convexa asociado con la formulación. Se muestra que todas las desigualdades presentadas en este trabajo definen facetas bajo condiciones generales.Se estudia además el rango disyuntivo de las familias de desigualdades presentadas en este trabajo, asociado al operador BCC definido por Balas, Ceria y Cornuéjols. Se propone en esta tesis un concepto complementario al de rango disyuntivo, llamado anti-rango disyuntivo de una desigualdad válida. Este parámetro es de interés como medida teórica de la calidad de la desigualdad, y se estudian los anti-rangos disyuntivos de las desigualdades presentadas en este trabajo.
author2 Marenco, Javier
author_facet Marenco, Javier
Braga, Mónica Andrea
format Tesis doctoral
Tesis doctoral
acceptedVersion
author Braga, Mónica Andrea
author_sort Braga, Mónica Andrea
title Estudio poliedral del problema de coloreo acíclico
title_short Estudio poliedral del problema de coloreo acíclico
title_full Estudio poliedral del problema de coloreo acíclico
title_fullStr Estudio poliedral del problema de coloreo acíclico
title_full_unstemmed Estudio poliedral del problema de coloreo acíclico
title_sort estudio poliedral del problema de coloreo acíclico
publisher Universidad Nacional de General Sarmiento
publishDate 2019
url http://repositorio.ungs.edu.ar/handle/UNGS/256
work_keys_str_mv AT bragamonicaandrea estudiopoliedraldelproblemadecoloreoaciclico
_version_ 1769989244432941056

Ejemplares similares