[Coin-discuss] Experiences with paralleling simplex

[Esben Mose Hansen]

On Friday 05 January 2007 19:56, Jonathan Eckstein wrote:

> I have experience parallelizing simplex, but it was before COIN existed.
>   See
>
> Data-Parallel Implementations of Dense Simplex Methods on the Connection
> Machine CM-2, J. Eckstein, I. Boduroglu, L. Polymenakos, and D.
> Goldfarb. ORSA Journal on Computing 7(4):402-416 (1995).
>
> However, as you can see from the title, this work was for dense
> problems, which are rare in practice.  Parallelizing general sparse

indeed. The problem in question are quite sparse.

> simplex methods has proved extremely challenging.  A lot of very good
> people have worked on it, and the results have not been spectacular.
> The amount of speedup you need (6x) may be possible, depending on your
> problem, but it is definitely not a project for the non-expert.

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 :)


> I would first recommend first trying your problems in a top-level
> commercial product like CPLEX or XPRESS.  These may be sufficiently fast
> that you won't need further speedup.  Another option is to use a barrier
> method.  I know CPLEX barrier has a parallel option for shared-memory
> parallel machines.  Also, I believe Jacek Gondzio's group has a nice
> (non-commercial, I think) framework for barrier methods, where you can
> obtain parallelism by inserting the parallel linear equation solver of
> your choice.

ok, thank you. Going for cplex might not be a viable solution, depending on 
the costs.  

>
> I don't know if barrier is as efficient as simplex for your problem, but
> since it appears to be very large, there is a good chance it will be.
> However, if the minimization problems are closely related, and simplex
> is taking advantage of that, then barrier may not be competitive.  There
> is some very recent work on warm-starting barrier methods (Benson &
> Shanno, or Gondzio et al.) that might apply in this case.

The (25ish) problems are definitely related, but this is definitely worth 
looking into.

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

-- 
kind regards, Esben Mose Hansen