ILOG describes that many MIPs can be solved >= 1.7 times
faster using multiple threads and shared memory.
http://www.ilog.com/optimization/the-right-hand-side/1/TA_Parallel_CPLEX_Dong.html
http://www.ilog.com/optimization/the-right-hand-side/1/TA_Parallel_CPLEX_Dong.html
Probably if a machine has more than one cpu. However, it is a brute
force approach. (It would help if the machine has 2^n processors, where
n is the number of binary variables :) Try to solve gesa2 or gesa3
from miplib without and with mir cuts. That what's I mean.
This is not only brute force. Parallel branch-and-bound can be seen as
multiple searches in the whole B&B domain. With chance, one of the
searches may find a good solution faster than sequential search on a
single core, since the search order may be different. Multiplying the
number of search threads not only enables the use of several cores, but
also raises the chance for faster finding a near-optimum solution,
quickly reducing the size of the search space, and helping find the
optimum faster.
In case of column generation (like in the CLSP) multiple
subproblems could be solved at the same time on separate
cores.
My understanding is that a major group of functions that
has a problem with threading is the memory allocation
(xfree, ...).
See
http://lists.gnu.org/archive/html/help-glpk/2007-08/msg00040.html
http://lists.gnu.org/archive/html/help-glpk/2007-08/msg00040.html
Yes, because different threads would use the same memory pool
implemented by xmalloc/xfree. This might be resolved by storing
the 'tls' pointer (defined in glplib02.c) in the thread local
storage.
The Bob++ parallel algorithm framework I am contributing to has a
parallel B&B which can be used for MIP solving. It can make use of GLPK
for solving LP bounds in the different B&B nodes. For now we used a
patched version of GLPK where xmalloc/xfree simply use the C malloc/free
calls. Recent versions of Glibc make use of very effective
thread-friendly memory allocators, which drastically reduce overhead due
to multithreading, using techniques such as caching, making malloc/free
perfect for multithreading, and removing all needs for TLS-like memory
allocation.
However, our patched version may still be broken, since we hadn't
noticed the strtok and strerror issue.
see http://bobpp.prism.uvsq.fr/
--
François Galea
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
