Orientador: Clovis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-25T01:09:27Z (GMT). No. of bitstreams: 1
Podesta_ValeriaAbraode_D.pdf: 3666244 bytes, checksum: 1835bad12b2cd2f4f460f94767c6052b (MD5)
Previous issue date: 1999 / Resumo: O problema de Multifluxo (Fluxo de Multiproduto) em uma rede é um modelo de Programação Matemática com muitas aplicações práticas. Neste trabalho, apresentamos um estudo computacional do Método Primal-Dual de Pontos Interiores aplicado ao problema de Multifluxo. Destacamos a resolução do sistema linear das direções, onde é utilizado o método dos Gradientes Conjugados com uma combinação dos precondicionadores Diagonal e Floresta Geradora Máxima. Vários experimentos computacionais foram realizados, incluindo duas regras de atualização do parâmetro de centragem, três pontos iniciais e critérios de parada no Gradiente Conjugado, entre outros. Apresentamos ainda a caracterização da base de Multifluxo, uma heurística para a obtenção de uma base ótima a partir de uma solução interior "quase-ótima" fornecida pelo Método Primal-Dual e um estudo sobre a degenerescência / Abstract: The Multicommodity Flow Problem is a model of Mathematical Programming defined on a network that has many important applications. In this work, we perform a computational study of a Primal-Dual Interior Point Method applied to this problem. We solve the linear system of iterate displacements using the Conjugate Gradient Method with a combination of the preconditioned Diagonal and Maximum Spanning Forest. Several computational experiments were performed, considering different starting points, different rules of the centering parameter update and different stopping criterion for the Conjugate Gradient. We present a characterization of the Multiflow basis, a heuristic for constructing an optimal basis from an interior "quasi-optimal" solution given by the Primal-Dual Method as well as a study about degeneracy / Doutorado / Doutor em Matemática Aplicada
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/306870 |
| Date | 25 July 2018 |
| Creators | Podestá, Valéria Abrão de, 1953- |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Perin Filho, Clovis, 1947-, Arenales, Marcos Nereu, Oliveira, Aurelio Ribeiro Leite de, Martínez Pérez, José Mario, Moretti, Antonio Carlos |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática Aplicada |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 196 p., application/pdf |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds