Defesa de Tese de Doutorado da aluna Luisa Silveira Rosa
Título da Tese: Algoritmo Básico Híbrido para Programação Binária Não Linear Irrestrita
Resumo: Hammer, Rosemberg, and Rudeanu propuseram o Algoritmo Básico (BA), uma abordagem algébrica para resolver problemas de Programação Não Linear Binária Irrestrita. Este algoritmo elimina variáveis sequencialmente enquanto calcula seus gradientes em função das variáveis restantes. Depois, como segundo passo, recupera as soluções ótimas. A complexidade do algoritmo está intimamente ligada à largura da árvore associada ao grafo de concorrência da função, onde os vértices representam as variáveis binárias e as arestas conectam variáveis que aparecem no mesmo produtório. Para controlar a largura da árvore associada a instância, o Algoritmo Básico foi incorporado a uma estrutura de branch-and-bound. Demonstramos que, no pior caso, a melhor estratégia em termos de tempo de execução do algoritmo é realizar todas as enumerações de variáveis antes da eliminação. A seleção das variáveis utilizadas na enumeração é baseada no conceito de Centralidade do grafo. Além disso, uma heurística gulosa determina a sequência de eliminação das variáveis restantes. Um processo para estimar o tempo total de execução foi desenvolvido visando dimensionar o tamanho do subconjunto de variáveis a serem enumeradas. O algoritmo resultante, chamado de Algoritmo Básico Híbrido (HBA), também foi usado como uma heurística, utilizando um conjunto maior de variáveis na enumeração. Finalmente, mostramos a eficácia do HBA por meio das seguintes aplicações: os problemas do Corte Máximo, de Sequências Binárias de Baixa Autocorrelação e do Determinante Máximo de Hadamard. Os resultados para o problema da baixa correlação se sobrepuseram sob os do PQCR (Elloumi et al., 2021). Além disso, comparamos os resultados do HBA com os resolvedores Antigone, Couenne e Gurobi. Seis instâncias da MINLPLib em aberto foram resolvidas, além de mais seis aprimoradas.
Orientador: Prof. Dr. Helio Côrtes Vieira Lopes
Banca: Prof. Dr. Marcus Vinicius Soledade Poggi de Aragao | Prof. Dr Eduardo Uchoa Barboza |
Prof. Dr Rafael Martinelli Pinto | Prof. Dr Ricardo Fukasawa | Prof. Dr Bruno Fânzeres dos Santos Prof. Dr Artur Alves Pessoa | Prof. Dr Jonatas dos Santos Grosman
Assista a defesa pelo link: https://puc-rio.zoom.us/j/91972972631?pwd=ZktreWVXVTVGbDgrRkFGeFV3UlUwUT09