Defesa de Doutorado do discente Danilo Santos Souza, dia 25/04/2024 às 13hs

Defesa de Doutorado do discente Danilo Santos Souza, dia 25/04/2024 às 13hs

Título: APPROACHING THE GENERALIZED ASSIGNMENT PROBLEM AND CUTTING-PLANE SEPARATION USING HETEROGENEOUS COMPUTING

This thesis presents innovative optimization approaches, combining both exact and heuristic techniques while enjoying heterogeneous computational resources. It focuses primarily on the Generalized Assignment Problem (GAP), wherein the allocation of jobs to agents with limited resources aims to minimize costs. The initial proposal harnesses the substantial computational capabilities of Graphics Processing Units to devise a method efficiently generating a solution pool using Tabu list criteria and an Ejection Chain mechanism, combined with Binary Programming Pool Search (BPPS). Experimental findings demonstrate the competitiveness of this approach against existing algorithms in the literature. Furthermore, we conducted several investigations and computational experiments to introduce novel cutting plane generators. These generators utilize heterogeneous resources and are designed to enhance MIP solvers as described in the existing literature. The results showed promise when applied to instances from the PSPLib and MIPLib, especially when compared with similar techniques from commercial solvers. Still in the context of GPU-based heuristics, we model three approaches based on the Multi-Improvement (MI) strategy for the GAP. MI on GPUs has been successfully applied to the classical Traveling Salesman Problem, modeled as a conflict graph. Thus, we propose a novel approach to MI for GAP with capacities, as agent capacities may interfere with the composition of MI moves, resulting in infeasible solutions. We believe this approach could open new avenues for future research in the field. Finally, we discuss the advantages and disadvantages of using parallel architectures, as well as the use of exact and heuristic techniques for the Generalized Assgiment Problem.

Data: 25 de abril de 2024 Horário: 13hs

Local: Link da videochamada: https://meet.google.com/pwm-fmwu-uto 

Banca: Prof. Dr. Puca Penna (UFOP), Prof. Dr. Gladston Juliano Prates Moreira (UFOP); Prof. Dr. Marco Antônio (UFOP), Prof. Dr. Ueverton Souza (UFF); Prof. Dr. Igor Machado (UFF), Prof. Dr. Rian Pinheiro (UFAL)