Melhorando a eficiência do método de pontos interiores preditor-corretor

Resumo

Os métodos de pontos interiores têm sido extensivamente estudado e utilizado para resolver problemas de programação linear de grande porte nas últimas décadas. Entre todas as suas variações, o método Preditor-Corretor apresenta um grande destaque, devido a sua eficiência e convergência rápida. Neste método, dois sistemas de equações lineares são resolvidos em cada iteração, para determinar a direção de busca, denominada direção preditora-corretora. Resolver estes sistemas lineares corresponde ao passo que requer mais tempo de processamento, devendo assim ser resolvido de forma eficiente. Os objetivos principais deste projeto consistem em melhorar o desempenho do método Preditor-Corretor, reduzindo o tempo computacional e/ou o número total de iterações e também resolver problemas de programação linear, que ainda não foram resolvidos por outras abordagens. Sendo assim, é fundamental otimizar o tempo de resolução dos sistemas lineares e aumentar a robustez do método. Para isso, várias técnicas serão estudadas, desenvolvidas e aperfeiçoadas, tais como, eliminação de linhas redundantes, iterações continuadas, algoritmo de ajustamento ótimo, métodos iterativos alternativos para resolução de sistemas lineares, abordagem híbrida de pré-condicionamento dos sistemas lineares. Todas as implementações serão incorporadas ao software PCx, o qual é uma implementação do método de pontos interiores Preditor-Corretor com múltiplas correções. O código do PCx é aberto e foi desenvolvido no Optimization Technology Center at Argonne National Laboratory and Northwestern University. A maioria das suas rotinas são implementadas na linguagem C. Diversos experimentos computacionais serão realizados utilizando variados problemas de programação linear de livre acesso na internet pertencentes a diferentes coleções. (AU)