bnb/MPIBranchAndBound.h
Header of the layer bnb, in the group Searches; the same header on the site of Doxygen, its source on GitHub.
Classes
Class |
Description |
|---|---|
The distributed B&B with one MPI process per worker |
Concepts
-
template<class P>
concept MPIBranchAndBound - #include <PBeFS/bnb/MPIBranchAndBound.h>
a B&B problem whose nodes and values can travel between processes
The values are trivially copyable, and travel as their bytes; either the node is trivially copyable too, or the problem gives serialize( n , out ), which appends the bytes of the node n to the std::vector< char > out, and deserialize( in ), which rebuilds a node from the bytes at the const char * in and moves in past them.
Description of the header
Header file for MPIBranchAndBound, the distributed Branch-and-Bound (B&B) with one MPI process per worker: each process has a queue of open nodes and sends the children to their owners, as DistributedBranchAndBound does with threads [see ParallelBranchAndBound.h] and HDAStarMPI with the states of A* [see HDAStarMPI.h].
The problem, the options and the Solution are those of BranchAndBound.h and ParallelBranchAndBound.h, and the design is discussed in docs/branch-and-bound.md.
The search is the following, with the notation of the page “Parallel
branch-and-bound” of the documentation, the procedures of the sequential search [see
BranchAndBound.h] and DIVE of the parallel ones [see ParallelBranchAndBound.h], on the process \( i \) of \( p \), with its queue \( Q_i \), whose least bound is written βmin(Q_i), and the incumbent \( z \) known to it: 1 procedure MPI-B&B(R_i) on the process i ▷ R_i: its own nodes
2 Q_i ← R_i; d ← nil
3 loop
4 for each message m received do
5 if m is a batch of nodes then push them in Q_i
6 else if m is an incumbent z' then z ← min(z, z')
7 else if m is a stop then stop evaluating
8 if not stopped and (d ≠ nil or not PRUNABLE(βmin(Q_i))) then
9 n ← d, or the first node of Q_i, removed; d ← nil
10 K ← PROCESS(n), a value v < z sending v to all the others
11 d ← DIVE(K)
12 for each m ∈ K but d do
13 j ← hash(m) mod p, or a random process without hash(m)
14 if j = i then push m in Q_i else send m to j
15 every k evaluations, send the outboxes not yet full
16 if the share of the node limit or the time limit is reached
then stop all the processes
17 else send all the outboxes
18 if the mailbox detects the end then break
19 the nodes still travelling, after a stop, are put in Q_i
20 the process of the least z sends its node to all
When no node of \( Q_i \) can improve \( z \) (lines 8 and 18) the nodes of \( Q_i \) become leaves (pruned), and after a stop the nodes left in \( Q_i \) are leaves (open), which bound the optimum. The end is detected by the four-counter method of Mattern in the mailbox of ADS, which by line 18 a process joins only when it has nothing to evaluate and nothing to send; every process gets the same incumbent, value and bound, and keeps the leaves that it owns.
- Author
Donato Meoli
Dipartimento di Informatica
Università di Pisa
- Copyright
© by Donato Meoli