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)