Banca de DEFESA: GABRIEL LOPES LIMA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
STUDENT : GABRIEL LOPES LIMA
DATE: 03/03/2022
TIME: 14:00
LOCAL: Online
TITLE:
KEY WORDS:

Max-Cut Problem. Exact approach. Binary search tree. Metaheuristics.

PAGES: 81
BIG AREA: Engenharias
AREA: Engenharia de Produção
SUMMARY:

The maximum cut problem is one of the combinatorial problems widely discussed in the literature. In this problem, given an undirected and weighted graph 𝐺 = (𝑉,𝐴), we seek to partition the set of vertices into two subsets, such that the sum of the weights of the edges connecting the two subsets is maximized. Despite the simplicity of its definition, the maximum cut problem is NP-Complete, being also classified as NP-Hard, that is, a class of problems that so far have not defined a method to find an optimal solution in polynomial time of deterministic way. Thus, to solve these highly complex problems, metaheuristic approaches are most often used. Thus, unlike algorithms already proposed in the literature, and aiming to explore the possibility of a new exact approach, which is mathematically interconnected, capable of exploring the space of solutions and finding the optimal solution for the problem, this study proposes a new exact approach with a search tree algorithm and develop five metaheuristic algorithms for solving the max-cut problem. This research was divided into four phases, where, in the first phase, the development and implementation of the exact approach to the solution of the problem was performed. In the second phase, five metaheuristics were implemented. In the third phase, computational experiments were conducted with different types of graph instances. Finally, in the fourth phase, statistical analysis was performed. The results showed that for the max-cut solution, the existing metaheuristic methods still present a better tradeoff between finding a good solution and the time needed to do so because in this first version of the ABB algorithm, the complexities are still very to solve instances of denser graphs, to solve this challenge of complexity it is necessary to further explorations in the algorithm to find a new contradiction criterion, so that it is viable to find the optimal solution of the problem in acceptable times for any graph.

BANKING MEMBERS:
Presidente - 2732514 - ISIS DIDIER LINS
Interno - 1078937 - RAPHAEL HARRY FREDERICO RIBEIRO KRAMER
Externo à Instituição - REINALDO MORABITO NETO