[Coin-discuss] Experiences with paralleling simplex

[Jonathan Eckstein]

Dear Esben:

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

I am aware of work by Bixby and Martin (INFORMS J. Computing, 2000),
Helgason and Kennington (Annals of OR, 1988), but there is plenty of
other work.

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.

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.

   -- Jonathan Eckstein


Esben Mose Hansen wrote:
> Hi,
> 
> I am looking at some options to bring down runtime for an application from max 
> 3h to about 0.5h. One of the options would be to run the application using 
> several processors. Most of the application's runtime is used in solving a 
> fairly large linear minimisation problem several times. Talking with my 
> colleagues about, it seems reasonable that the simplex algorithm could be 
> paralised. 
> 
> Do anyone here have any experience with paralising linear minimisation with 
> coin, or maybe with other libraries? Any pointers, experiences and especially 
> outright implementations would be very, very welcome.
> 
> One idea would be to attack the  pivoting. After the pivot row has been 
> selected, this row is then used to manipulate the entire matrix; one could 
> imagine splitting up the matrix in say 4 parts, handing each quarter to a 
> separate process. Each would find the best pivot row in their part of the 
> matrix, and then transfer the result to the other processes, after which the 
> best pivot (row) could be used to manipulate the matrix, and so forth.
>