Metodo primal-dual de pontos interiores aplicado ao problema de multifluxo
Valeria de Podesta Gomes
TESE
Português
T/UNICAMP P751m
Campinas, SP : [s.n.], 1999.
196 p.
Orientador: Clovis Perin Filho
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
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...
Ver mais
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
Ver menos
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...
Ver mais
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
Ver menos
Perin Filho, Clovis, 1947-2023
Orientador
Arenales, Marcos Nereu
Avaliador
Martínez Pérez, José Mario, 1948-
Avaliador
Moretti, Antonio Carlos, 1958-
Avaliador
Metodo primal-dual de pontos interiores aplicado ao problema de multifluxo
Valeria de Podesta Gomes
Metodo primal-dual de pontos interiores aplicado ao problema de multifluxo
Valeria de Podesta Gomes
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra