[Coin-discuss] Experiences with paralleling simplex

[Michael Hennebry]

On Fri, 5 Jan 2007, Esben Mose Hansen wrote:

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


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

As noted by another, sparse simplex is
notoriously difficult to parallelize.

Find out how long a pivot takes now and compare it to the amount
of time needed to transfer a row or column between a pair of processors.
That should give you a clue to how much improvement is possible.

-- 
Mike   hennebry at web.cs.ndsu.NoDak.edu
"Finally, mount the partition, not the virgin."  --  Charles Curley