MPIBranchAndBound.h File Reference

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]. More...

#include <cstdint>
#include <cstring>
#include <random>
#include <span>
#include <type_traits>
#include <vector>
#include <mpi.h>
#include "ADS/distributed/MPIMailbox.h"
#include "PBeFS/bnb/ParallelBranchAndBound.h"

Go to the source code of this file.

Classes
class	MPIBranchAndBoundSearch< P >
	the distributed B&B with one MPI process per worker More...

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

Concepts
concept	PBeFS_di_unipi_it::MPIBranchAndBound
	a B&B problem whose nodes and values can travel between processes

Detailed Description

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