Reordenamento Estático na Atualização da Decomposição LU no Método Simplex
DOI:
https://doi.org/10.5540/tema.2007.08.02.0211Abstract
Neste trabalho são desenvolvidas técnicas de atualização da decomposição LU da base no método Simplex, utilizando um reordenamento estático nas colunas da matriz. Uma simulação do método Simplex, realizando troca de colunas básicas obtidas pelo MINOS e verificando sua esparsidade é implementada. Somente os elementos afetados pela mudança de base são considerados para obter uma atualização da decomposição LU eficaz. As colunas da matriz são reordenadas de acordo com o n´umero de elementos não nulos, em ordem crescente e na forma bloco triangular. Assim, obtém-se uma decomposição esparsa para qualquer base sem esforço computacional para obter a ordem das colunas, pois o reordenamento da matriz é estático e as colunas da base obedecem esta ordem. O objetivo deste trabalho é comparar a simulação desenvolvida que considera a esparsidade da matriz com os resultados obtidos pelo MINOS. Resultados computacionais em Matlab para problemas da Netlib mostram que esta idéia é muito promissora, pois não são necessárias refatorações periódicas como nos métodos de atualização tradicionais.References
[1] R. Bartels, A stabilization of the simplex method, Numer. Math., 16 (1971), 414-434.
G. Bressan, A. Oliveira, Fast iterations for the combined cutting-stock and lot-sizing problems, Anais da IX International Conference on Industrial Enginnering and Operations Management, Arq. TI0601, (2003), 1-8.
G. Bressan, A. Oliveira, Reordenamento eficiente das colunas básicas na programa ção de lotes e cortes, Pesquisa Operacional, 4 (2004), 323-337.
I. Duff, A. Erisman, J. Reid, “Direct methods for sparse matrices”, Clarendon Press, Oxford, 1986.
J.L. Kennington, R.V. Helgason, “Algorithms for Network Programming”, Wiley, New York, 1980.
H. Markowitz, The elimination form of the inverse and its applications to linear programming, Management Science, 3 (1957), 255-269.
I. Maros, “Computational Techniques of the Simplex Method”, Kluwer Academic Publishers, 2003.
S.L. Nonas, A. Thorstenson, A combined cutting-stock and lot-sizing problem, Operations Research, 120 (2000), 327-342.
J. Reid, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases, Mathematical Programming, 24 (1982), 55-69.
C.T.L. Silva, “Problemas de Otimização Linear Canalizados e Esparsos”, Dissertação de Mestrado, ICMC, USP, São Carlos, 2002.
U. Suhl, L. Suhl, A fast lu update for linear programming, Annals of Operations Research, 43 (1993), 33-47.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.