Técnicas de Modelagem Para Resolução de Problemas de Otimização Combinatória

Resumo

Em diversas áreas surgem problemas práticos que podem ser enunciados como problemas de otimização combinatória, tais como transporte, produção industrial, logística, análise de dados biológicos, etc. Existe uma vasta literatura sobre diferentes abordagens de modelagem para resolução de problemas de otimização combinatória, tais como ProgramaçãoLinear Inteira (PLI) e Programação Por Restrições (PPR). Essas abordagens têm sido utilizadascom bastante sucesso na resolução de diversos problemas NP-difíceis e, recentemente, novosmétodos que unem conceitos dessas duas abordagens têm sido propostos na literatura. Nesteprojeto, apresentamos alguns problemas de otimização combinatória para os quais pretendemosdesenvolver modelos de PLI e PPR. Pretendemos investigar esses problemas de um ponto devista teórico, no sentido de encontrar explicações teóricas para justificar nossas abordagens, e prático, no sentido de realizar experimentos computacionais de forma a possibilitar o uso prático de nossos métodos. Esses problemas podem ser dividos em dois tópicos, sendo um deles os problemas de cobertura e empacotamento em grafos bipartidos, e o outro o problema de cobertura de matrizes por raios extremais. Apresentamos aplicações desses problemas nas áreas de produção industrial e análise de dados biológicos, resultados relacionados encontrados na literatura, nossos resultados preliminares e os resultados esperados. Está previsto em nosso projeto um estágio de pesquisa no exterior.