Problema da coloração de vértices com pesos dissonantes e restrições de cores

Detalhes bibliográficos
Ano de defesa: 2023
Autor(a) principal: EDISON GABRIEL GONÇALVES BORGHEZAN
Orientador(a): Edna Ayako Hoshino
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Fundação Universidade Federal de Mato Grosso do Sul
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Brasil
Palavras-chave em Português:
Link de acesso: https://repositorio.ufms.br/handle/123456789/6596
Resumo: 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.