Re: [Help-glpk] Multithreading/parallelization

[Robbie Morrison]

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]