Orientadores: Aurelio Ribeiro Leite de Oliveira, Carla Taviane Lucke da Silva Ghidini

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica

Resumo: Os métodos de pontos interiores têm sido amplamente utilizados para determinar a solução de problemas de programação linear de grande porte. O método preditor corretor, dentre todas as variações de métodos de pontos interiores, é um dos que mais se destaca, devido à sua eficiência e...

Resumo: Os métodos de pontos interiores têm sido amplamente utilizados para determinar a solução de problemas de programação linear de grande porte. O método preditor corretor, dentre todas as variações de métodos de pontos interiores, é um dos que mais se destaca, devido à sua eficiência e convergência rápida. Este método, em cada iteração, necessita resolver dois sistemas lineares para determinar a direção preditora corretora. Resolver estes sistemas lineares corresponde ao passo que requer mais tempo de processamento, devendo assim ser realizada de forma eficiente. Para resolver estes sistemas lineares a abordagem mais utilizada é a fatoração de Cholesky. No entanto, realizar a fatoração de Cholesky em cada iteração tem um alto custo computacional. Dessa forma, na busca de redução de esforços, precisamente, na redução do número de iterações foi desenvolvida a iteração continuada. Iteração continuada é uma iteração subsequente, realizada após o cálculo da direção preditora corretora, onde é determinada uma nova direção sem que seja necessário realizar uma nova fatoração de Cholesky. Os resultados computacionais dos testes realizados, principalmente em problemas de médio e grande porte mostraram que esta abordagem obtém bom desempenho em comparação com o método preditor corretor

Abstract: Interior point methods have been widely used in the solution of large linear programming problems. The predictor corrector method, among ali interior point variants, is one of mostly used due to its efficiency and convergence properties. This method needs the solution of two linear systems...

Abstract: Interior point methods have been widely used in the solution of large linear programming problems. The predictor corrector method, among ali interior point variants, is one of mostly used due to its efficiency and convergence properties. This method needs the solution of two linear systems to determine the predictor corrector direction, in each iteration. Solving such systems corresponds to the step which requires more processing time. Therefore, it should be done efficiently. The most common approach to solve the linear systems is the Cholesky factorization, demanding in each iteration a high computacional effort. Thus, in search of effort reduction, in particular, to reduce the iterations number continued iteration was developed. The continued iteration is a subsequent iteration performed after the predictor corrector direction is computed, where a new direction is calculated without need to of Cholesky refactorization. The numerical tests show that the continued iteration performs better in comparison with the preditor corretor method