[Coin-discuss] Experiences with paralleling simplex

[Jonathan Eckstein]

Esben Mose Hansen wrote:

> Can you give me a clue to what makes the sparse case harder than the dense? I 
> must admit, I did not even suspect that any difficulty might arise from this 
> aspect :)

The matrices are not stored in the format one might assume from reading 
elementary textbooks on simplex.  The matrix is usually stored by column 
in a sparse format, using pairs of the form (rownumber,coefficient), for 
each nonzero.  The "tableau" found in textbooks is not stored, but 
instead some representation of the basis matrix B that makes solving 
equations of the form B x = r or tranpose(B) y = c efficient.  Some kind 
of sparse LU factorization is typical.  The trickiest calculation is 
updating this factorization with each pivot.  Simplex is also a really 
tricky algorithm to implement, with many numerical pitfalls.

Unless the problem is unusually dense (as sometimes happens in data 
analysis applications, but is otherwise very rare), an implementation 
that uses naive matrix storage will be totally uncompetitive, even with 
a lot of parallelism.

> ok, thank you. Going for cplex might not be a viable solution, depending on 
> the costs.  
> 
> The (25ish) problems are definitely related, but this is definitely worth 
> looking into.

Depending on how they're related, there also might be the option 
sticking each problem on its own processor, and solving them in 
parallel.  That would not be so hard with COIN.

> Thank you for your response. It seems this is quite harder than I naively 
> thought.

You're welcome.  It is not just a programming project, that is for sure.

   J E