PPGI | (92) 3305-1181 Ramal 1193 / (92) 99128-5875 |
Convite 53ª Defesa de Doutorado - Bruno Raphael Cardoso Dias
Quarta-feira, 09 Outubro 2019,  2:00 -  6:00
Contato: Secretaria do PPGI (Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.)

A Coordenação do Programa de Pós-graduação em Informática PPGI/UFAM tem o prazer de convidar toda a comunidade para a sessão pública de apresentação da 53ª Defesa de Tese de Doutorado

TÍTULO: Colorações em Grafos com Restrições de Distância: Caracterizações, Politopos e Estratégias em Programação Matemática

CANDIDATO: Bruno Raphael Cardoso Dias

BANCA EXAMINADORA:

Profa. Rosiane de Freitas Rodrigues -  IComp/UFAM (Presidente)
Prof. Dr. Altigran Soares da Silva- IComp/UFAM
Prof. Dr. Edleno da SIlva Moura - IComp/UFAM
Prof. Dr. Geraldo Robson Mateus - DCC/UFMG
Prof. Dr. Manoel Campelo- DC/UFC
Prof. Dr. Javier Leonardo Marenco - FCEN/UBA, UNGS (Argentina)

RESUMO:

Coloração em grafos constitui uma das classes de problemas de otimização combinatória de maior relevância teórica e prática, com variações envolvendo restrições adicionais nos vértices ou arestas. Uma das aplicações mais importantes ocorre em telecomunicações, envolvendo a alocação de canais em redes móveis sem fio, na qual canais devem ser atribuídos a um conjunto de dispositivos, de modo a se evitar interferências. O problema de coloração em largura de banda (do inglês, Bandwidth Coloring Problem - BCP) modela o caso geral de tal aplicação, onde vértices adjacentes recebem cores diferentes mas tais cores devem respeitar uma separação imposta por meio de pesos nas arestas, generalizando o problema clássico de coloração de vértices em grafos (do inglês, Vertex Coloring Problem - VCP). No entanto, este modelo não aborda todos os casos aplicáveis à alocação de canais, possibilitando a utilização de outros ferramentais teóricos para identificar novos modelos. Sendo assim, nesta tese, são caracterizados novos problemas de coloração de vértices com restrições adicionais de distâncias, baseados em conceitos de geometria de distâncias e teoria dos grafos, com tipos de restrições de adjacência envolvendo igualdades e desigualdades, e valores arbitrários e uniformes para representar as distâncias, aplicáveis a diferentes características da alocação de canais, como comunicação uni e bidirecional. Estes modelos teóricos definem uma grande subclasse de problemas de colorações com distâncias em grafos, para a qual foram estabelecidas algumas propriedades de factibilidade e complexidade computacional. Formulações de programação por restrições foram propostas com base nas definições dos problemas abordados, com o uso de restrições globais na presença de múltiplas demandas de cores por vértices, bem como formulações em programação inteira, onde uma já existente foi refinada e outras duas novas foram propostas, baseadas em orientações do grafo de entrada e nas distâncias entre cores atribuídas. Ambas formulações propostas possuem tamanho polinomial, ao contrário dos modelos existentes que são pseudo-polinomiais. Um estudo poliedral foi realizado onde, para os novos politopos correspondentes, são definidas propriedades e algumas famílias de desigualdades válidas que induzem a facetas sob determinadas condições. Para avaliar o impacto de tais formulações matemáticas, estratégias computacionais exatas foram utilizadas, com destaque para um algoritmo cut-and-branch desenvolvido com base no politopo de orientação e nas desigualdades válidas propostas. Experimentos realizados utilizando instâncias do BCP e de alocação de canais da literatura (com e sem múltiplas demandas de cores por vértices) permitiram estabelecer melhores limites superiores para determinadas instâncias,  com a prova de otimalidade de soluções heurísticas apresentadas na literatura, e principalmente a obtenção de novos ótimos para outros casos . Foi realizada uma análise comparativa entre as estratégias de programação inteira e por restrições, considerando a presença ou não de múltiplas demandas de cores por vértices. Por fim, foi possível verificar que as novas formulações, em especial a baseada em orientação e o método cut-and-branch, permitiram a obtenção de soluções ótimas em menor tempo de execução para diversas instâncias utilizadas, estabelecendo assim que os novos modelos têm bom potencial para solucionar problemas de colorações com distâncias. Os resultados obtidos fornecem contribuições importantes em geometria de distâncias, combinatória poliédrica e teoria dos grafos para a classe de problemas de colorações de vértices em grafos. Os resultados foram divulgados em eventos nacionais e internacionais e publicados nos periódicos ITOR, RAIRO, DAM, LNCS, ENDM e Matemática Contemporânea, com versões preliminares disponibilizadas na Optimization Online e arXiv.

Local Auditório 02 - ICompTech

Produzido por :