Matheuristics para o problema do conjunto de vértices de retroalimentação de peso mínimo e para o problema da b-coloração
metaheurísticas, conjunto de vértices de retroalimentação, $b$-coloração de grafos, programação inteira mista, \textit{matheuristic}
Nesta dissertação de mestrado, propõe-se novas \textit{matheuristics} para dois problemas NP-difíceis de otimização combinatória em grafos. O primeiro problema estudado é o problema do conjunto de vértices de retroalimentação de peso mínimo (MWFVS, do inglês \textit{minimum weighted feedback vertex set}). Dado um grafo valorado $G=(V,E)$, o MWFVS consiste em obter um subconjunto de peso mínimo $F\subseteq V$ cuja remoção torna o grafo acíclico. Diferentemente de outras abordagens na literatura, este trabalho trata o problema através da floresta induzida de peso máximo (MWIF, do inglês \textit{maximum weighted induced forest problem}). Primeiramente, propõe-se duas novas formulações compactas de programação inteira mista (MIP, do inglês \textit{mixed integer programming}), que utilizam um número polinomial de variáveis e restrições. Em seguida, desenvolve-se uma \textit{matheuristic} que combina uma metaheurística \textit{multi-start} baseada em busca local iterativa com um procedimento de busca local baseado em MIP. Esta dissertação também considera o problema da $b$-coloração. Dado um grafo $G=(V,E)$, o mesmo consiste em atribuir cores à cada vértice em $V$ tal que vértices adjacentes recebam cores diferentes, todas as cores possuam um $b$-vértice, e o número de cores seja máximo. Um $b$-vértice é um vértice adjacente a vértices coloridos com todas as cores exceto a sua própria. O número $b$-cromático de $G$, denotado $\rchi_b$, é determinado pela solução ótima do problema da $b$-coloração. Apresenta-se uma formulação de programação inteira e uma heurística gulosa randomizada que é altamente efetiva quando usada de forma \textit{multi-start}. Além disso, uma \textit{matheuristic} é proposta combinando a heurística com a formulação de programação inteira. Experimentos computacionais mostram que as técnicas propostas para ambos os problemas superam as metaheurísticas estado da arte para a maioria das instâncias testadas.