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

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.