Estudo e implementação de variantes do método primal-dual simplex

Resumo

A programação linear é a principal área da otimização. Ela oferece métodos de solução poderosos capazes de resolver problemas de grande escala com alta confiabilidade e em tempo computacional razoável. Os dois métodos mais importantes para resolução de problemas de programação linear são o método simplex e o método de pontos interiores. Até o momento, as variantes primais-duais tem mostrado clara vantagem na prática por conseguir controlar melhor o progresso do algoritmo utilizando simultaneamente as soluções dos problemas primal e dual. Variantes primais-duais do método simplex foram menos exploradas na literatura e elas se baseiam em numa perspectiva primal-dual diferente. Nesse projeto é proposto um algoritmo primal-dual que, similarmente ao método primal-dual de pontos interiores, reúne informações das soluções primais e duais em cada iteração do algoritmo. Outras variantes do método primal-dual simplex são abordadas e seus algoritmos e desempenho prático são comparados com o método proposto por meio de experimentos computacionais utilizando instâncias da biblioteca Netlib. As comparações são realizadas para destacar as vantagens e desvantagens de cada método primal-dual e mostrar seus potenciais benefícios para resolver diferentes tipos de problemas de programação linear. Essa pesquisa será orientada pelo Professor Jacek Gondzio na Universidade de Edimburgo, na Escócia - Reino Unido. (AU)