[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Multithreading/parallelization

From: Reginald Beardsley
Subject: Re: [Help-glpk] Multithreading/parallelization
Date: Sun, 16 Dec 2012 19:28:56 -0800 (PST)

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!

--- 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:
> 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
>   + 61 3 5222 3435

reply via email to

[Prev in Thread] Current Thread [Next in Thread]