Título: Métodos de solução para o problema de coloração de fluxo

Data: 06/02/2019

Horário: 14:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Considere um grafo $G$ com uma certa demanda de fluxo a ser enviada de alguns vértices de origem a um vértice de destino. Chamamos de fluxo viável uma transmissão de fluxo através dos vértices e arestas de $G$ que satisfaz a demanda. Cada fluxo viável define um multigrafo com os vértices e arestas de $G$, mas com a multiplicidade de cada aresta sendo igual à quantidade de fluxo que passa por essa aresta no fluxo viável. Uma solução viável do problema de coloração de fluxo é composta por um fluxo viável e uma atribuição de cores às arestas do seu respectivo multigrafo tal que duas arestas adjacentes recebem cores distintas. O objetivo do problema é encontrar uma solução viável onde a coloração das arestas tenha o menor número de cores distintas. Neste trabalho, apresentamos um método aproximativo para esse problema que melhora o fator de aproximação 3/2 do algoritmo de Campelo et al. (2012), até então a melhor garantia de aproximação encontrada na literatura. Para esse propósito, definimos um novo problema, a ser solucionado em uma das etapas do nosso algoritmo, que provamos poder ser resolvido em tempo polinomial. Apresentamos duas novas formulações de programação inteira para o problema de coloração de fluxo, adaptamos uma terceira, proposta inicialmente para um problema relacionado, e realizamos um estudo teórico das três formulações. Propomos uma heurística, baseada no método de geração de colunas, que pode ser implementada com duas das formulações estudadas. Apresentamos experimentos computacionais realizados com as duas versões da heurística, mostrando que ambas obtêm, de forma bastante eficiente, soluções com valor muito próximo ao ótimo. Por fim, introduzimos um algoritmo exato, baseado no método de branch-and-cut, que utiliza uma das formulações estudadas e duas desigualdades que provamos serem válidas para essa formulação.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)
• Prof. Dr. Carlos Diego Rodrigues (UFC)
• Prof.ª Dr.ª Ana Shirley Ferreira da Silva (UFC)