Qualificação de mestrado do discente Pedro Lucas Damasceno, dia 16/12/2025 às 13:30.

Qualificação de mestrado do discente Pedro Lucas Damasceno, dia 16/12/2025 às 13:30.

Título: Minimização de blocos consecutivos com parallel tempering e algoritmo Lin-Kernighan-Helsgaun
Resumo: O problema de minimização de blocos consecutivos consiste em determinar uma permutação das colunas de uma matriz binária de modo a minimizar o número de blocos de 1 consecutivos em cada linha. Esse problema apresenta aplicações em diversas áreas, como organização de arquivos, programação de linhas de produção, escalonamento e compressão de dados. Por se tratar de um problema de otimização combinatória NP-difícil, métodos aproximados têm se mostrado mais adequados para sua resolução. Neste contexto, este estudo descreve o desenvolvimento de um algoritmo baseado na aplicação da metaheurística parallel tempering sobre soluções iniciais geradas pelo algoritmo Lin-Kernighan-Helsgaun, após a conversão do problema em um traveling salesman problem utilizando a matriz de distâncias de Hamming. Trabalhos futuros desenvolverão a implementação do método de forma detalhada, a parametrização dos componentes, a comparação com os melhores resultados reportados pelo atual estado da arte e as lacunas a serem preenchidas por trabalhos subsequentes.

Data: 16/12/2025
Horário: 13h30
Banca Avaliadora: Prof. Marco Antonio M. Carvalho, Prof. Leonardo Cabral da Rocha Soares