Métodos para Resolução de Problemas de Otimização Quadráticos Binários

Resumo

Neste projeto, investigamos os problemas de Programação Quadrática Binária Irrestrita (UBQP) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB), que pertencem à classe de complexidade NP-difícil. Em virtude de apelos práticos, há grande interesse no desenvolvimento de métodos para resolver esses problemas. Com o intuito de contribuir de maneira significativa para esta área de pesquisa, pretendemos: (a) desenvolver um método exato para o problema UBQP; (b) projetar um algoritmo de tempo polinomial para resolver classes de instâncias do problema UBQP; (c) propor uma versão paralela dos métodos indicados nos itens (a) e (b); (d) desenvolver uma fórmula para gerar limitantes aos valores de soluções ótimas para resolver instâncias do problema UBQP; (e) desenvolver fórmulas para calcular rapidamente o valor da função objetivo do problema BQP-GUB; e (f) converter problemas de otimização para a forma dos problemas UBQP e BQP-GUB. Embora estes objetivos sejam ambiciosos, ressaltamos que nos últimos seis meses obtivemos resultados originais com relação aos itens (a), (b), (d), (e) e realizamos experimentos computacionais quanto aos itens (a) e (b). Estes resultados preliminares, teóricos e computacionais, são animadores.