Re: [Help-glpk] GLPK re-endrant

[François Galea]

> > 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