Re: [Help-glpk] Multithreading/parallelization

[Reginald Beardsley]

Fools rush in where wise men fear to tread.  Many thanks for the warning.

After looking at a number of Julian Hall's slide sets, I've become rather 
skeptical of attempting to parallelize the simplex method in glpk.  For n>>m he 
makes the assertion that it is very difficult to improve on a good serial 
revised simplex implementation with partial pricing. 

Moreover, papers by Pingqi Pan suggest that other rules may be faster than even 
partial pricing, though he's unclear about the implications for cycling.  In 
any event this leads me to conclude that focusing on improving serial 
performance might be more fruitful.  When I posed the question, I had assumed 
that glpk was pretty much at the limits of serial performance already.

Along the way I came across:

"Computational Techniques of the Simplex Method"
 by István Maros

Does anyone have any experience w/ this book?

I'd be grateful for any guidance anyone might have to offer.

Thanks,
Reg

--- On Sun, 12/16/12, Meketon, Marc <address@hidden> wrote:

> From: Meketon, Marc <address@hidden>
> Subject: RE: [Help-glpk] Multithreading/parallelization
> To: "Reginald Beardsley" <address@hidden>, "glpk" <address@hidden>
> Date: Sunday, December 16, 2012, 11:54 AM
> A lot of later responses have been
> focused on the multi-threading issues from a data structure
> viewpoint.
> 
> Yet to speed up a single, large, linear program, I would
> think that the discussion would have been on the use of
> multiple cores to speed up the factorization, pricing and
> other components of the simplex algorithm.
> 
> Googling "parallel simplex algorithm" gives some papers on
> attempts to speed up the simplex algorithm (e.g., 
> http://www.maths.ed.ac.uk/hall/HEG10/HEG10.pdf)
> 
> The general message seems to be that parallelization of LU
> factorization is difficult.  The pricing part is
> trivial to parallelize.  There are other possibilities
> listed (such as task parallelism).
> 
> Parallelization within the MIP branch and bound and
> parallelization of interior point algorithms have been done
> successfully.  Not sure how true it is for the
> simplex.  Does anyone have experience or knowledge of
> speeding up the simplex using multi-cores?
> 
> -----Original Message-----
> From: address@hidden
> [mailto:address@hidden
> On Behalf Of Reginald Beardsley
> Sent: Friday, December 14, 2012 2:24 PM
> To: glpk
> Subject: [Help-glpk] Multithreading/parallelization
> 
> What is the status of multithreading or parallelization
> support in glpk and glpsol in particular?  I've found a
> good bit of prior discussion, but nothing recent.
> 
> Is there intent to do this or a desire not to do it? 
> I'm gradually wandering into solving ever larger problems
> which will probably put considerable pressure on me to speed
> things up.
> 
> If there is an interest in taking advantage of multicore
> processors, has anyone done any profiling of a
> representative problem suite to identify what routines would
> benefit most?  I'm pretty familiar w/ what needs to be
> done and have growing incentive to do at least some of the
> work.
> 
> Reg
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
> 
> This e-mail and any attachments may be confidential or
> legally privileged. If you received this message in error or
> are not the intended recipient, you should destroy the
> e-mail message and any attachments or copies, and you are
> prohibited from retaining, distributing, disclosing or using
> any information contained herein.  Please inform us of
> the erroneous delivery by return e-mail. Thank you for your
> cooperation.
>