Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/46819
Tipo: Dissertação
Título: Métodos para solução do problema de coloração de fluxo
Título em inglês: Methods for solving the flow coloring problem
Autor(es): Matias, Jhonata Adam Silva
Orientador: Campêlo Neto, Manoel Bezerra
Palavras-chave: Otimização combinatória;Coloração de fluxo;Fluxo em rede;Coloração de arestas
Data do documento: 2019
Citação: MATIAS, Jhonata Adam Silva. Métodos para solução do problema de coloração de fluxo. 2019. 71 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2019.
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 algoritmo aproximativo que fornece uma solução viável para o problema de coloração de fluxo com até ʟ(5X'ϕ + 2)/4˩ cores, onde X'ϕ é o número ótimo de cores. O fator de aproximação desse algoritmo melhora o fator 3/2 do algoritmo de Campêlo 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 de forma direta 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, sugerimos 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.
Abstract: Consider a graph G with a certain demand of flow to be sent from some source vertices to a target vertex. We call feasible flow a transmission of flow through the vertices and edges of G that meets the demand. Each feasible flow defines a multigraph with the vertices and edges of G, but with the multiplicity of each edge being equal to the amount of flow passing through that edge in the feasible flow. A feasible solution of the flow coloring problem consists of a feasible flow and an assignment of colors to the edges of its respective multigraph such that any two adjacent edges receive different colors. The goal of the problem is to find a feasible solution whose edge coloring has the least number of distinct colors. In this work, we present an approximation algorithm for the flow coloring problem that always uses fewer than ʟ(5X'ϕ + 2)/4˩ colors, where X'ϕ is the optimal number of colors. The approximation ratio of that algorithm improves the previous best ratio, 3/2, given by an algorithm by Campêlo et al. (2012). For this purpose, we have defined a new problem, which is solved in a step of our algorithm, and we prove that it can be solved in polynomial time. We present two novel integer linear programming formulations for the flow coloring problem and directly adapt a third one, initially proposed for a closely related problem. We also present a theoretical study of that three formulations. We propose a column generation based heuristic that can be implemented with two of the formulations studied. We present computational experiments performed with the two versions of the heuristic which shows that both can obtain, efficiently, solutions very close to the optimum. Finally, we suggest an exact algorithm, based on the branch-and-cut method, that uses one of the studied formulations and two inequalities that we have proved to be valid for this formulation.
URI: http://www.repositorio.ufc.br/handle/riufc/46819
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2019_dis_jasmatias.pdf600,43 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.