Contribution of the LU factorization update in the Simplex method / Contribuição da atualização da decomposição LU no metodo Simplex

AUTOR(ES)

Daniela Renata Cantane

DATA DE PUBLICAÇÃO

2009

RESUMO

Finding efficient solution of linear systems is fundamental in the linear programming problems and the first method to obtain success for this class of problems was the Simplex method. With the objective to develop efficient alternatives to its implementation, techniques of the simplex basis LU factorization update are developed in this thesis to improve the solution of the Simplex method linear systems towards a matrix columns static reordering. A simulation of the Simplex method is implemented, carrying through the change of basis obtained from MINOS and verifying its sparsity. Only the factored columns actually modified by the change of the base are carried through to obtain an efficient LU factorization update. The matrix columns are reordered according to three strategies: minimum degree; block triangular form and the Björck strategy. Thus, sparse factorizations are obtained for any base without computational effort to obtain the order of columns, since the reordering of the matrix is static and base columns follow this ordering. The application of the block triangular form achieved the best results, for larger scale problems tested, in comparison to minimum degree method and the Björck strategy. Computational results for Netlib problems show the robustness of this approach and good computational performance, since there is no need of periodical factorizations as used in traditional updating methods. The proposed method obtained a reduction of the nonzero entries of the basis with respect to MINOS. This approach was applied in the cutting stock problems and the proposed method achieved a reduction of the computational time in the solution of such problems with respect to the GLPK.

ASSUNTO(S)

decomposição lu lu factorization update programação linear linear programming simplex (matematica) simplex method

Documentos Relacionados

• Uma contribuição ao método de síntese modal experimetal
• Contribuição ao estudo de painéis reforçados: comparação entre o método da chapa ortotrópica e o método dos elementos finitos.
• The contribution of manufacturing industry in software development
• Contribuição ao estudo da interação de campos eletromagneticos e tecidos biologicos utilizando o metodo de diferenças finitas no dominio do tempo
• Uma contribuição para a modelagem numérica da heterogeneidade do concreto com o método de Galerkin livre de elementos.