Orientador: Christiano Lyra Filho

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação

Resumo: O presente trabalho faz um estudo cuidadoso dos métodos de pontos interiores para obter implementações eficientes na solução de problemas de fluxo de custo mínimo. Tendo em vista que a maior parte do esforço computacional dos algoritmos baseados nos métodos de pontos interiores é dedicado à...

Resumo: O presente trabalho faz um estudo cuidadoso dos métodos de pontos interiores para obter implementações eficientes na solução de problemas de fluxo de custo mínimo. Tendo em vista que a maior parte do esforço computacional dos algoritmos baseados nos métodos de pontos interiores é dedicado à solução de sistemas do tipo AD* ATY = b, é feita uma análise deste sistema, explorando-se as características da estrutura de redes. Implementa-se especializações dos métodos diretos e dos métodos iterativos. Os métodos diretos são especializações da decomposição de Choleski. Heurísticas do tipo grau mínimo e preenchimento local mínimo são usadas para reordenação das linhas e colunas, procurando conservar a esparsidade da matriz AD* AT. Para a família dos problemas de transportes e atribuição, desenvolve-se um método de ordenação ótima. Os métodos iterativos são do tipo gradiente conjugado pré-condicionado. A estrutura de rede permite agilizar o cálculo das direções, reduzir requisitos de memória e construir pré-condicionadores bem informados. Um pré-condicionador do tipo diagonal é usado nos primeiros passos dos métodos de pontos interiores. Quando a solução se aproxima da otimalidade, constrói-se um outro pré-condicionador, baseado em estimações sobre a base ótima. Desenvolve-se implementações especializadas à problemas de fluxo de custo mínimo dos métodos primal afim, dual afim, primal dual e preditor-corretor. Interpretações baseadas no método de Newton para solução de problemas não lineares levaram a inovações nas implementações dos métodos afins. Estuda-se o problema de falta de volume (ou falta de pontos interiores), aspecto frequente em problemas de fluxo de custo mínimo. Avalia-se suas conseqüências na utilização de métodos de pontos interiores. A partir dos experimentos computacionais com os códigos desenvolvidos, procura-se fazer uma sistematização dos problemas em classes, com indicação das melhores alternativas de solução para cada classe.Finalmente, faz-se extensões das idéias desenvolvidas para a resolução de problemas de fluxos generalizados, através de métodos de pontos interiores

Abstract: This work is a careful study of the interior point methods looking for eflicient implementations for network flow linear programs. Computational experiments are developed with the primal afline, dual afline, primal dual and predictor-corrector methods looking for the best alternatives for...

Abstract: This work is a careful study of the interior point methods looking for eflicient implementations for network flow linear programs. Computational experiments are developed with the primal afline, dual afline, primal dual and predictor-corrector methods looking for the best alternatives for different classes of problems. We discuss Newton's method interpretations of these methods. Since most of the computational time of the interior point methods is spent solving systems of the type (AD* AT)y = b, for different diagonal matrices D* and the same incidence matrix A we take advantage of the structure of such systems for networks. We use the sparse Cholesky factorization with two heuristics: the minimum degree and local minimum fill-in. For the family transportation and assignment problems, it is developed an optimal ordering method. We also use the conjugate gradient method with diagonal and maximum spanning tree preconditioners. We give particular attention to the degenerescency phenomena mainly to the lack of primal and/or dual interior feasible points. We study their consequences to interior point methods. Finally proposes extensions of the main ideas to the generalized network problems