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 for the minimum weighted feedback vertex set and $b$-coloring problems

PALAVRAS-CHAVES:

 metaheuristics, feedback vertex set, graph $b$-coloring, mixed integer programming, matheuristics

PÁGINAS: 77
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

In this thesis, we propose new matheuristics for two NP-hard graph optimization problems. The first studied problem is denoted the minimum weighted feedback vertex set problem (MWFVS), for which given a weighted graph $G=(V,E)$ it consists in obtaining a minimum weight subset $F\subseteq V$ of the vertex set whose removal makes the graph acyclic. Differently from other approaches in the literature, we tackle this problem via the maximum weighted induced forest problem (MWIF). First, we propose two new compact mixed integer programming (MIP) formulations, using a polynomial number of variables and constraints. Next, we develop a matheuristic that hybridizes a multi-start iterated local search metaheuristic with a MIP-based local search procedure. This thesis also studies the $b$-coloring problem, for which given a graph $G=(V,E)$ it consists in attributing a color to every vertex in $V$ such that adjacent vertices receive different colors, every color has a $b$-vertex, and the number of colors is maximized. A $b$-vertex is a vertex adjacent to vertices colored with all used colors but his own. The optimal solution of the $b$-coloring problem determines the $b$-chromatic number of $G$, denoted $\rchi_b$. We present an integer programming formulation and a very effective multi-greedy randomized heuristic which can be used in a multi-start fashion. Furthermore, a matheuristic is proposed combining the heuristic with the integer programming formulation. Extensive computational experiments show that the proposed techniques for both problems outperform the state-of-art metaheuristics for the majority of tested instances.

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