[Coin-discuss] Re: Experiences with paralleling simplex

[Esben Mose Hansen]

On Monday 08 January 2007 07:47, Erling D. Andersen wrote:

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

ok. That does explain why it seemed a simple thing to do on the surface, yet 
many people in here warning me it is non-trivial. 

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

The paper sound  very interesting, though to be honest I don't know if I can 
pursue this avenue now that I have established that it is not-at-all-trivial.

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

Hotstarts are probably are something we are looking into, and as for the 
dual/primal we already did this optimisation. I'm not sure exactly what an 
interior point optimizer would be.

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

Ok. We have not really investigated barrier (or any other interior point 
method). 

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

I believe so, but I will check up on it. In the case of the MIP solver we do 
presolve, but I'm not positive about the pure LP path.

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

Thank you. And thanks for your insights :)

-- 
kind regards, Esben