Re: [Help-glpk] Multithreading/parallelization

[Meketon, Marc]

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.