Defesa de Tese de Doutorado de Murilo Brugger Stockinger, 09/03/26, 14h, por videoconferência
Link para defesa: https://meet.google.com/ifa-rdxr-zrg
Making Heuristics and Exact Methods More Efficient with Data Mining
Resumo:
Esta tese investiga a integração de técnicas de mineração de dados em heurísticas e em métodos exatos, propondo estratégias orientadas por padrões para aumentar a eficiência da busca por soluções em problemas de otimização combinatória.
Como contribuição inicial, é proposto um novo método construtivo para o Problema da Floresta de Steiner, explorando uma estratégia de pareamento pivot-destino combinada com um mecanismo dinâmico de compartilhamento de custos. A partir desse método, desenvolvem-se as heurísticas GRASP-SFP e MDM-GRASP-SFP, esta última incorporando mineração de padrões frequentes a partir de um conjunto elite de soluções para guiar a intensificação da busca. Resultados computacionais demonstram que a utilização de padrões levou a uma redução média de 12,9% no tempo de execução, com ganhos de até 42,5%, sem perda de qualidade das soluções.
A principal contribuição da tese é a proposta de uma nova abordagem, denominada Pattern-Driven Branch-and-Bound, que utiliza padrões extraídos de soluções heurísticas de elite para orientar decisões de ramificação em métodos exatos. Diferentemente de abordagens híbridas baseadas em aprendizado supervisionado, a estratégia proposta explora conhecimento estrutural específico da instância durante a execução do próprio algoritmo. A abordagem proposta prioriza a seleção das variáveis contidas no padrão para abertura dos nós do processo de Branch-and-Bound e prioriza a atribuição do valor 1 para essas variáveis, sem abrir mão da otimalidade no processo de busca. Experimentos conduzidos nos problemas da floresta de Steiner e de roteamento de veículos capacitados evidenciam uma melhor eficiência na exploração do espaço de busca e no fortalecimento dos limitantes inferiores, demonstrando o potencial promissor da integração entre mineração de padrões e algoritmos de otimização.
Abstract:
This thesis investigates the integration of data mining techniques into both heuristics and exact methods, proposing pattern-driven strategies to enhance search efficiency in combinatorial optimization problems.
As an initial contribution, a novel constructive method for the Steiner Tree Problem is proposed, exploring a pivot-destination pairing strategy combined with a dynamic cost-sharing mechanism. Based on this method, the GRASP-SFP and MDM-GRASP-SFP heuristics are developed; the latter incorporates frequent pattern mining from an elite set of solutions to guide search intensification. Computational results demonstrate that the utilization of patterns led to an average reduction of 12.9% in execution time—with gains reaching up to 42.5%—without compromising solution quality.
The main contribution of this thesis is the proposal of a novel approach termed Pattern-Driven Branch-and-Bound, which utilizes patterns extracted from elite heuristic solutions to guide branching decisions within exact methods. Unlike hybrid approaches based on supervised learning, the proposed strategy exploits instance-specific structural knowledge during the algorithm’s execution. This approach prioritizes the selection of variables contained within the pattern for node branching and favors assigning the value of 1 to these variables, all while maintaining the optimality of the search process. Experiments conducted on the Steiner Tree Problem and the Capacitated Vehicle Routing Problem evidence improved efficiency in search space exploration and the strengthening of lower bounds, demonstrating the promising potential of integrating pattern mining with optimization algorithms.
Banca examinadora:
Profa. Isabel Cristina Mello Rosseti, UFF – Presidente
Prof. Alexandre Plastino de Carvalho, UFF
Prof. Yuri Abitbol de Menezes Frota, UFF
Prof. Igor Machado Coelho, UFF
Prof. Pedro Henrique González Silva, UFRJ
Prof. Anand Subramanian, UFPB