RE: [Help-glpk] Sparse vs. Dense problems

[Meketon, Marc]

Dense versus sparse is not a precise science.  For example, it is
well-known that a single dense column creates problems for interior
point algorithms.  Many interior point algorithms nowadays typically try
to identify dense columns and split them apart or (less typically)
algebraically separate them.  That is because interior point methods
need to solve system of equations like AA'w = y, where A is the m x n
"A" matrix in the LP, A' is its transpose, y is m-vector of knowns, and
w is an m-vector of unknowns.  And a single dense column in A makes AA'
dense.

Interior point algorithms think of a problem as sparse if the Cholesky
factorization of AA' = LL' (L is a lower triangular matrix) is sparse
(that is, L is sparse), possibly after dense columns are split.  But
that's not even the entire story because the ordering rows of A affect
the sparsity of L.

There is no scientific rule about when interior point algorithms work
better than extreme-point algorithms.  Certain problems always work
better with one algorithm compared to the other, but its hard to
generalize this.  Interestingly, over the years some problems that at
first seemed to only be solvable by interior-point algorithms are now
solvable (and faster) by extreme-value algorithms.  Competition between
these two algorithms have helped the entire optimization field.

-Marc

-----Original Message-----
From: address@hidden
[mailto:address@hidden On
Behalf Of Dragos Ilie
Sent: Saturday, August 02, 2008 12:00 PM
To: address@hidden
Subject: [Help-glpk] Sparse vs. Dense problems

Hi!

According to the GLPK manual the interior-point solver is fit for 
solving sparse LP problem and is quite inefficient for dense problems.

My understanding is that a sparse problem is one where most of the 
entries in the coefficient matrix are zero. Conversely, a dense problem 
has mostly non-zero entries in the coefficient matrix. Is this correct? 
Is there  a more accurate definition or rule quantifying what "most" 
entries means in terms of the size of the matrix?

Regards,
Dragos


_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------