Re: [Help-glpk] Multithreading/parallelization

[Harley Mackenzie]

Although I intend to write a much better specification for the proposed
project once I have done the research, I think there is some confusion
here. I was proposing multi-threaded operation on mulitple core
processors rather than processing over multiple processors using one of
the MP libraries. This may be later stage but not planned yet.

The last table of results show a median speed up of 3 times faster with
the 12 core test machine with hyper threading turned off (I suspect it
may have been better with hyper threading on) and the maximum speed up
was 20 times.

I would be very interested in what other techniques the commercial codes
use in comparison to GLPK. There has been some public disclosure about
this, and I am attempting to get hold of these papers. I don't expect
these papers to be very detailed but there may be some hints as to the
sort of areas that have been developed.

Harley

On Mon, Dec 17, 2012, at 19:39, Robbie Morrison wrote:
> 
> Hello Andrew, all
> 
> ------------------------------------------------------------
> To:           Reginald Beardsley <address@hidden>
> Subject:      Re: [Help-glpk] Multithreading/parallelization
> Message-ID:  <address@hidden>
> From:         Andrew Makhorin <address@hidden>
> Date:         Mon, 17 Dec 2012 09:49:18 +0400
> ------------------------------------------------------------
> 
> > Though parallelization allows reducing the
> > solution time, in my opinion, it is a brute
> > force approach (at least for problems which glpk
> > is intended to solve); moreover, since in case
> > of hard mips the solution time grows
> > exponentially, this approach helps not so much
> > (until you have 2**n processors, where n is the
> > number of integer variables :).  It seems to me
> > that algorithmic solutions are able to provide
> > much greater performance.
> 
> This email is pretty much a repeat of my posting
> on 04 Sep 2012, archived at:
> 
>   http://lists.gnu.org/archive/html/help-glpk/2012-09/msg00010.html
> 
> Figure 4 (p120) in Koch etal (2012) supports
> Andrew's view.  Proprietary solvers on multiple
> cores often performed *very much* worse in terms
> of elapsed time, nodes explored, and memory
> consumption.  It looks like multi-core hardware
> only starts to pay off over about 16 cores.
> 
>   Koch, Thorsten, Tobias Achterberg, Erling Andersen,
>       Oliver Bastert, Timo Berthold, Robert E Bixby,
>       Emilie Danna, Gerald Gamrath, Ambros M Gleixner,
>       Stefan Heinz, Andrea Lodi, Hans Mittelmann, Ted
>       Ralphs, Domenico Salvagnin, Daniel E Steffy, and
>       Kati Wolter.  2011.  MIPLIB 2010 : mixed integer
>       programming library version 5.  Mathematical
>       Programming Computation v3 no2 p103-163.
>       doi:10.1007/s12532-011-0025-9
> 
>       http://mpc.zib.de/index.php/MPC/article/viewFile/56/28
> 
> Robbie
> ---
> Robbie Morrison
> PhD student -- policy-oriented energy system simulation
> Technical University of Berlin (TU-Berlin), Germany
> University email (redirected) : address@hidden
> Webmail (preferred)           : address@hidden
> [from Webmail client]
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
-----
  Dr. Harley Mackenzie
  HARD software

  address@hidden
  www.hardsoftware.com
  + 61 3 5222 3435