[Coin-discuss] Experiences with paralleling simplex

[Esben Mose Hansen]

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.

-- 
kind regads, Esben