Re: [Help-glpk] Multithreading/parallelization

[Reginald Beardsley]

Thanks.  I was out of town at the time and missed it in the backlog.

I noticed in profiling the examples that trick.mod seems to get into trouble.  
I killed it after an hour, but I'm going to look at what's happening.  
Interestingly it completes in 100 seconds using --pcost.

Algorithm matters a lot in problems like these.  I was doing large (10**6 
points)  Delauney triangulations using Renka's TRIPACK code from TOMS and had a 
problem go into an infinite loop because of floating point issues.  I 
discovered the problem after having jobs run for several days w/o completing. I 
had run the code many times prior to that case. It took quite a bit of work to 
develop a small example. Fortune's sweep algorithm doesn't encounter a problem.

FWIW The Delauney triangulation in n dimensions is the projection of the convex 
hull in n+1 dimensions.  So there are very important connections between linear 
programming and computational geometry.

In light of the trick.mod behavior, parallelizing multiple heuristics for the 
MIP problem might be a big practical gain.  Setup the problem, solve the LP 
case and then spawn multiple MIP threads which all terminate when one succeeds. 
 Pingqi Pan's results suggest that a similar strategy might be useful for 
simplex as well.  Certainly not what I had in mind when I raised the subject, 
but if you're solving lots of instances, mean time to solution is what matters.

Have Fun!
Reg

--- On Sun, 12/16/12, Harley Mackenzie <address@hidden> wrote:

> From: Harley Mackenzie <address@hidden>
> Subject: Re: [Help-glpk] Multithreading/parallelization
> To: "Reginald Beardsley" <address@hidden>
> Cc: "GLPK-HELP" <address@hidden>
> Date: Sunday, December 16, 2012, 6:09 PM
> This was posted:
> 
>   Meindl and Templ (2012) solver survey by Robbie
> Morrison Nov 06, 2012;
>   09:36pm
> 
>   Meindl, Bernhard and Matthias Templ.  2012.
>       Analysis of commercial and free and
> open
>       source solvers for linear optimization
>       problems.  Report.  23
> February 2012.
> 
> download:
> http://neon.vb.cbs.nl/casc/..%5Ccasc%5CESSNet2%5Cdeliverable_solverstudy.pdf
> 
> Recommended reading, especially the number of the MIP
> problems solved by
> GLPK compared to the commercial codes.
> 
> Harley
> 
> On Sun, Dec 16, 2012, at 9:56, Reginald Beardsley wrote:
> > What recent paper? 
> 
> -- 
> -----
>   Dr. Harley Mackenzie
>   HARD software
> 
>   address@hidden
>   www.hardsoftware.com
>   + 61 3 5222 3435
>