IJPAM: Volume 60, No. 3 (2010)



State University of Campinas (UNICAMP)
400, Albert Einsten Av., Campinas, 13083-852, SP, BRAZIL

Abstract.In this work we develop simplex basis LU update
factorization techniques, using a static reordering of the matrix
columns. In the static reordering, the matrix columns are
rearranged in accordance with the increasing number of nonzero
entries, leading to sparse factorization of the basis without
computational effort to reorder the columns. Therefore the matrix
reordering is static and the columns of the basis follow this
ordering. A simulation of the simplex iterations is carried
through according to the base sequence obtained from MINOS. The
factorization and LU update are performed considering sparsity.
The objective of this work is to compare the developed reordering
approach with the results from MINOS. Preliminary computational
results in Matlab for problems from the Netlib collection show
that this is a very promising idea, since there is no need to
refactorize the matrix in the tested problems.
Received: February 12, 2007
AMS Subject Classification: 49N05
Key Words and Phrases: linear optimization, sparse matrix, factorization update, simplex
Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2010
Volume: 60
Issue: 3