Qualificação de mestrado do discente Jean Carlos Campos, dia 31/07/17.

Qualificação de mestrado do discente Jean Carlos Campos, dia 31/07/17.

Título: "Novos modelos e uma heurística relax-and-fix para o Problema da Árvore Geradora Mínima Capacitada em Níveis"
Data: 31/07/2017
Horário: 17h
Banca: Marcone Jamilson Freitas Souza (Orientador), Haroldo Gambini Santos
Resumo:
Este trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN). Ele consiste em encontrar uma árvore geradora de custo mínimo, tal que o fluxo a ser transferido de um nó central aos demais nós seja limitado pela capacidade das arestas. Para resolvê-lo, propomos neste trabalho uma nova formulação de programação matemática e um algoritmo híbrido, combinando o método Variable Neighborhood Search (VNS) e um modelo matemático. A formulação matemática proposta, chamada ''Modelo Baseado na Capacidade das Facilidades 2'' (MBC2), é baseada na formulação considerada a mais eficiente da literatura. A motivação para a utilização do modelo MBC2 está em fornecer um limite inferior de qualidade, esperando assim convergir mais rapidamente à solução ótima. Experimentos computacionais mostraram que a formulação proposta, quando comparado ao modelo da literatura, melhora a qualidade da relaxação linear, fornecendo assim um limite inferior melhor e justificando a sua utilização. Para o desenvolvimento do algoritmo híbrido, foi utilizado o modelo MBC2 proposto neste trabalho, em razão da sua capacidade de proporcionar um limite inferior de qualidade. A formulação é usada para fornecer uma solução inicial ao VNS. Resultados mostram que o VNS melhora a solução inicial e gera soluções com gaps relativamente pequenos nas instâncias usadas para teste.