IJPAM: Volume 60, No. 3 (2010)

AN EFFICIENT SIMPLEX LU FACTORIZATION UPDATE

Daniela R. Cantane$^1$, Aurelio R.L. Oliveira$^2$
$^{1,2}$School of Electric Engineering and Computation (FEEC)
State University of Campinas (UNICAMP)
400, Albert Einsten Av., Campinas, 13083-852, SP, BRAZIL
$^1$e-mail: dcantane@densis.fee.unicamp.br


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