• Apresentação
  • Linhas de Pesquisa
  • Teses e Dissertações
  • Corpo Docente
Principal
  • Home
  • Apresentação
  • Regimento Interno e Normas
  • Corpo Docente
  • Teses e Dissertações
  • Linhas de Pesquisa
  • Grupos de Pesquisa
  • Notícias
  • Infraestrutura
  • Contatos
Processo Seletivo
  • Inscrições
  • Informações Gerais
  • Editais e Portarias
  • Áreas e Sub-Áreas
  • Calendário
  • Resultados
Alunos
  • Oferta de Disciplinas
  • Integralização Curricular
  • Normas de Exame de Qualificação
  • Normalização de Trabalhos Acadêmicos
Home Notícias Defesa de Tese: Ernando Gomes de Sousa

Defesa de Tese: Ernando Gomes de Sousa

Seg, 12 de Agosto de 2019 00:00 | Escrito por Secretaria MDCC | PDF | Imprimir | E-mail

Título: Multigraph, decomposition and BRKGA solution approaches for the Generalized Minimum Spanning Tree Problem

Data: 14/08/2019

Horário: 14:00h

Local: Sala de Videoconferência - STI

Resumo:

Given a connected, undirected, and m-partite graph G = (V1 ∪ V2 ∪ ... ∪ Vm, E), with vertex set partitioned into disjoint subsets V 1,V 2, ...,V m and whose edges of E connect only nodes of distinct clusters, the Generalized Minimum Spanning Tree Problem (GMSTP) looks for a minimum-cost tree with exactly m - 1 edges, connecting V1,V 2, ...,Vm through the selection of exactly one vertex of each cluster. The GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This work presents an original multigraph mathematical formulation, a new procedure for eliminating vertices proved to not belong to an optimal solution, a BRKGA meta-heuristic and a Benders decomposition method applied to an existing flow-based formulation for the GMSTP. Computational results for the multigraph formulation present better results than for existing formulations for the problem. Moreover, the Benders decomposition presents the best results among all the analysed strategies, as well as BRKGA presents better performance than existing metaheuristics for GMSTP. This, with respect to solution quality for benchmark instances of the problem. Finally, this work opens new directions for research and the development of algorithms for related problems.

Banca:

  • Prof. Dr. Rafael Castro de Andrade (MDCC/UFC - Orientador)
  • Profª. Drª. Andréa Cynthia Santos Duhamel (Université du Havre)
  • Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
  • Prof. Dr. Abílio Pereira de Lucena Filho(UFRJ)
  • Prof. Dr. Philippe Yves Paul Michelon (Université d'Avignon)
 

Copyright © 2010-2011 MDCC-UFC.
All Rights Reserved.

Designed by Joomla Desk.