Defesa de Proposta de Tese de Doutorado de Fernando Bezerra Chagas, 11/04/2025, 14h, por videoconferência
Link para defesa: meet.google.com/fzd-usob-thx
Improving Heuristics and Exact Methods with Data Mining for Combinatorial Optimization Problems
Resumo:
Esta tese investiga a integração de técnicas de mineração de dados com métodos heurísticos e exatos para problemas de otimização combinatória, com foco em duas frentes principais. A primeira explora variações híbridas de meta-heurísticas que incorporam mineração de padrões para reduzir o espaço de busca e guiar a construção de soluções. Para isso, empregamos a abordagem MineReduce, que identifica padrões recorrentes em soluções de alta qualidade e os utiliza para restringir o problema de forma eficaz. Como estudo de caso, aplicamos essa técnica ao Problema da Máxima Diversidade (MDP), demonstrando melhorias relevantes na qualidade das soluções e no tempo de execução em comparação com heurísticas consagradas na literatura.A segunda frente busca aprimorar o algoritmo Branch-and-Bound (B&B) por meio da incorporação de estratégias baseadas em padrões extraídos de soluções heurísticas. Em particular, exploramos uma abordagem que utiliza mineração de padrões frequentes (FPM) para priorizar decisões de ramificação promissoras sem comprometer a otimalidade. Duas estratégias foram implementadas e testadas para o MDP, e os resultados indicam reduções significativas no espaço de busca e no tempo computacional, além da obtenção de melhores limitantes.Como continuidade deste trabalho, pretende-se aplicar essas estratégias a outros problemas, como o 2-Path Network Design Problem (2-PNDP), além de investigar novas técnicas voltadas à extração de conhecimento sobre regiões menos promissoras do espaço de busca, com o objetivo de guiar o B&B de forma mais eficiente.
Abstract:
This thesis investigates the integration of data mining techniques with heuristic and exact methods for combinatorial optimization problems, focusing on two main approaches. The first explores hybrid variations of metaheuristics that incorporate pattern mining to reduce the search space and guide the construction of solutions. To this end, we employ the MineReduce approach, which identifies recurring patterns in high-quality solutions and uses them to effectively restrict the problem. As a case study, we apply this technique to the Maximum Diversity Problem (MDP), demonstrating significant improvements in solution quality and execution time compared to well-established heuristics in the literature. The second approach aims to enhance the Branch-and-Bound (B&B) algorithm by incorporating strategies based on patterns extracted from heuristic solutions. In particular, we explore an approach that uses frequent pattern mining (FPM) to prioritize promising branching decisions without compromising optimality. Two strategies were implemented and tested for the MDP, and the results indicate significant reductions in both the search space and computational time, along with better bounds. As a continuation of this work, we aim to apply these strategies to other problems, such as the 2-Path Network Design Problem (2-PNDP), and investigate new techniques focused on extracting knowledge about less promising regions of the search space to guide the B&B algorithm more efficiently.
Banca examinadora:
Prof. Alexandre Plastino de Carvalho, UFF – Presidente
Profa. Isabel Cristina Mello Rosseti, UFF
Prof. Yuri Abitbol de Menezes Frota, UFF
Prof. Francisco Glaubos Nunes Clímaco, UFMA
Prof. Rafael Augusto de Melo, UFBA