Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/6596
Tipo: Dissertação
Título: Problema da coloração de vértices com pesos dissonantes e restrições de cores
Autor(es): EDISON GABRIEL GONÇALVES BORGHEZAN
Primeiro orientador: Edna Ayako Hoshino
Resumo: O problema de coloração de vértices com pesos dissonantes e restrições de cores é uma generalização do problema de coloração de vértices e vários outros problemas de coloração podem ser reduzidos a ele. Neste trabalho é proposta uma variação do problema de coloração de vértices, e também três modelos matemáticos utilizando programação linear inteira, um modelo cujo número de variáveis e restrições é polinomial, um segundo, no qual o número de variáveis é exponencial em relação ao número de restrições e um terceiro modelo bastante semelhante ao segundo mas que aproveita-se de uma propriedade que permite algumas cores serem aglutinadas almejando uma execução mais rápida. Para os modelos estendidos, são propostos algoritmos de geração de colunas para lidar com o número exponencial de variáveis do problema, assim como heurísticas, tanto para gerar novas colunas quanto para encontrar soluções inteiras em cada nó da árvore de enumeração para acelerar o desempenho de um algoritmo exato de branch-and-price. Um conjunto de instâncias foi proposto e foi possível identificar características das instâncias difíceis para este problema.
Abstract: The vertex coloring problem with dissonant weights and color constraints is a generalization of the vertex coloring problem and several other coloring problems can be reduced to it. This work proposes a variation of the vertex coloring problem, and also three mathematical models using integer linear programming, a model whose number of variables and restrictions is polynomial, and a second, in which the number of variables is exponential in relation to the number of restrictions and a third model very similar to the second but which takes advantage of a property that allows some colors to be combined for faster execution. For the extended models, column generation algorithms are proposed to deal with the exponential number of variables in the problem, as well as heuristic, both to generate new columns and to look for integer solutions on each node of the enumeration tree to accelerate the performance of the exact branch-and-price algorithm. A set of instances was proposed and it was possible to identify characteristics of the instances that are the most difficult ones for the problem.
Palavras-chave: Otimização combinatória, programação linear inteira, geração de colunas, grafos
País: Brasil
Editor: Fundação Universidade Federal de Mato Grosso do Sul
Sigla da Instituição: UFMS
Tipo de acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/6596
Data do documento: 2023
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo TamanhoFormato 
Versão_final c2.pdf598,25 kBAdobe PDFVisualizar/Abrir


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