Título: Métodos de solução para problemas quadráticos binários

Data: 31/08/2018 Horário: 14h30min Local: Sala de Seminários - Bloco 952

Resumo:

O objetivo principal desse trabalho é mostrar a aplicação de métodos das áreas de programação linear e não linear para tratar problemas que possuem em sua formulação natural uma função objetivo com termos quadráticos 0-1. Para este fim, desenvolvemos uma extensão da técnica da t-linearização para termos quadráticos com coeficientes arbitrários e mostramos como aplicá-la em problemas quadráticos binários (Corte Máximo, Diversidade Máxima e Clique Máxima Ponderada em Arestas). Adicionalmente, revisamos a técnica da suavização hiperbólica, usualmente empregada na solução de problemas não lineares contínuos, e mostramos como aplicá-la  ao problema do corte máximo. Realizamos um estudo teórico para cada problema, onde apresentamos o desenvolvimento de novas restrições válidas para cada um deles. Fizemos experimentos computacionais que atestam o desempenho das técnicas apresentadas e das novas restrições propostas. Os experimentos foram conduzidos para testar os limites obtidos, assim como a qualidade das novas restrições. Construímos um método exato para o problema da diversidade máxima e comparamos o nosso método com uma implementação nossa do melhor método exato conhecido da literatura. Os resultados favorecem o nosso método proposto. Podemos atestar que as técnicas mostradas fornecem novos caminhos para abordar problemas quadráticos 0-1.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
• Prof. Dr. Carlos Diego Rodrigues (UFC)
• Prof. Dr. Philippe Yves Paul Michelon (Université d'Avignon)