ParallelBranchAndBound.h File Reference

Header file for the parallel best-first searches with an incumbent, i.e., the parallel Branch-and-Bound (B&B) on an executor of ADS (the pool of C++ threads, OpenMP or FastFlow): SharedBranchAndBound, whose workers extract the nodes from one queue as the workers of SPA* do, and DistributedBranchAndBound, whose workers have a queue each and send the children to their owners as the workers of HDA* do. More...

#include <atomic>
#include <memory>
#include <mutex>
#include <random>
#include <type_traits>
#include "PBeFS/bnb/BranchAndBound.h"
#include "ADS/parallel/Channels.h"
#include "ADS/parallel/Mailbox.h"

Go to the source code of this file.

Classes
struct	BasicParallelBBOptions< V >
	the options of the parallel B&B with values of type V More...
class	BBIncumbent< Node, V >
	the incumbent shared by the workers of a parallel B&B More...
class	SharedBranchAndBound< P, Executor >
	the parallel B&B with one queue shared by the workers More...
class	DistributedBranchAndBound< P, Executor >
	the parallel B&B with a queue per worker and the children sent to their owners More...
struct	DistributedBranchAndBound< P, Executor >::Msg
	a node travelling to its owner More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Typedefs
using	ParallelBBOptions = BasicParallelBBOptions<>
	the options of the parallel B&B with values of type double

Detailed Description

Header file for the parallel best-first searches with an incumbent, i.e., the parallel Branch-and-Bound (B&B) on an executor of ADS (the pool of C++ threads, OpenMP or FastFlow): SharedBranchAndBound, whose workers extract the nodes from one queue as the workers of SPA* do, and DistributedBranchAndBound, whose workers have a queue each and send the children to their owners as the workers of HDA* do.

The problem, the options and the Solution are those of BranchAndBound.h, and the design is discussed in docs/branch-and-bound.md.

The two searches are the following, with the notation of the page "Parallel branch-and-bound" of the documentation and the procedures PROCESS and PRUNABLE of the sequential search [see BranchAndBound.h]; the incumbent \( z \) is shared (BBIncumbent), DIVE(K) is the child of \( K \) that the worker goes on with (the last one with depth-first, the one of least bound with plunging if it is close enough to the least open bound, none otherwise), and \( p \) is the number of workers:

 1  procedure SHARED(R)       ▷ one queue Q, under the lock L, for all
 2     Q ← R;  busy ← 0;  done ← false
 3     in parallel, on each worker i = 0, ..., p − 1 do
 4        d ← nil
 5        loop
 6           if d ≠ nil then n ← d;  d ← nil
 7           else n ← NEXT();  if n = nil then return
 8           if a limit is reached then
 9              n is a leaf (open);  busy ← busy − 1;  done ← true;  return
10           K ← PROCESS(n)
11           lock L;  d ← DIVE(K);  push the nodes of K but d in Q
12           if d = nil then busy ← busy − 1
13           unlock L
14  procedure NEXT()
15     loop
16        if done then return nil
17        if Q = ∅ then                             ▷ read without the lock
18           if busy = 0 then
19              lock L;  if Q = ∅ and busy = 0 then done ← true;  unlock L
20           else wait a little
21           continue
22        lock L
23        if PRUNABLE(the least bound of Q) then
24           the nodes of Q are leaves (pruned);  Q ← ∅;  unlock L
25           continue
26        busy ← busy + 1;  n ← the first node of Q, removed;  unlock L
27        return n
28  procedure DISTRIBUTED(R)  ▷ a queue Q_i per worker, nodes to the owners
29     put each node of R in the queue of its owner
30     in parallel, on each worker i = 0, ..., p − 1 do
31        d ← nil
32        while the search is not over do
33           push the nodes received in Q_i
34           if d ≠ nil then n ← d;  d ← nil
35           else if Q_i ≠ ∅ and not PRUNABLE(the least bound of Q_i) then
36              n ← the first node of Q_i, removed
37           else
38              the nodes of Q_i are leaves (pruned);  Q_i ← ∅
39              send all the outboxes;  wait for mail or the end; continue
40           if a limit is reached then n is a leaf (open); stop all; return
41           K ← PROCESS(n);  d ← DIVE(K)
42           for each m ∈ K but d do
43              j ← hash(m) mod p, or a random worker without hash(m)
44              if j = i then push m in Q_i else send m to j
45           every k evaluations, send the outboxes not yet full

The counter busy of the shared search is raised under the lock when a node is extracted (line 26) and lowered only after the children of the node have been pushed (line 12), so that \( Q = \emptyset \) and busy \( = 0 \), read under the lock at line 19, mean that no node is open anywhere. The distributed search detects its end at line 39 by the mailbox of ADS, when no worker has a node and no node is travelling; since a tree has no duplicates, the owner of line 43 only balances the load.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli