Banca de DEFESA: MICHELL FELIPPE FERNANDES MACEDO QUEIROZ
Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : MICHELL FELIPPE FERNANDES MACEDO QUEIROZ
DATA : 24/09/2019
HORA: 10:00
LOCAL: Sala 12 do IME
TÍTULO:
Matheuristics para o problema do conjunto de vértices de retroalimentação de peso mínimo e para o problema da b-coloração
PALAVRAS-CHAVES:
metaheurísticas, conjunto de vértices de retroalimentação, $b$-coloração de grafos, programação inteira mista, \textit{matheuristic}
PÁGINAS: 77
RESUMO:
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.
MEMBROS DA BANCA:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2250653 - TIAGO DE OLIVEIRA JANUARIO
Externo à Instituição - MARCIO COSTA SANTOS - UFC
Externo à Instituição - CELSO DA CRUZ CARNEIRO RIBEIRO - UFF
Externo à Instituição - CARLOS EDUARDO DE ANDRADE