[Coin-discuss] Re: Experiences with paralleling simplex

[Erling D. Andersen]

Hi

In theory it is very easy to parallelizing the simplex algorithm if you mean the test book
simplex algorithm. However, a practical implementation such as in the best code
employs a large number of tricks. Those tricks make it very hard to parallelize the algorithm.

Interior-point methods can be parallelized. MOSEK (our code) can exploit multiple CPUs
in fact as well can some of the other commercial codes. I have a paper about that if it is of any interest.

Usually we find you get much performance by investigating the following options carefully

  1.  An interior-point optimizer.
  2. Try both primal and dual  dual simplex.
  3. Check whether your hotstarts works properly. 


>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.

Usually those warmstart ideas will force you to shut presolve off. In many case the benefit 
you get presolve is much larger than what youu can get from hotstart. 

To Esben: I wonder if you problem can presolved a lot? Does you simplex optimizer
presolve when hotstarting?

MOSEK (our code) does not do that. But we have a development version that does that and in some cases
we got a speed-up of a factor 5 to 10. 

Feel free to send me some of you problems and I can give results for MOSEK interior-point optimizer
including parallel results.

Best regards/Venlig hilsen

Erling


*************************************************************************
MOSEK ApS     
C/O Symbion Science Park    
Fruebjergvej 3, Boks 16
DK-2100 Copenhagen O
Denmark

Phone (work): +45 3917 9907
Mobile-phone: +45 2362 9520
Fax:               +45 3917 9823
Email: e.d.andersen at mosek.com
Skype: erling.d.andersen
Homepage: http://erling.andersen.name 
                  http://www.mosek.com/homepages/e.d.andersen/

*************************************************************************