FarmBranchAndBound.h File Reference

Header file for FarmBranchAndBound, the master-worker Branch-and-Bound (B&B) on a farm with feedback on an executor of ADS: the master holds the queue of the open nodes, and the workers evaluate and branch the nodes it sends. More...

#include <atomic>
#include <memory>
#include <stdexcept>
#include <vector>
#include "PBeFS/bnb/ParallelBranchAndBound.h"
#include "ADS/parallel/Farm.h"

Go to the source code of this file.

Classes
class	FarmBranchAndBound< P, Executor >
	the master-worker B&B on a farm with feedback More...

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

Detailed Description

Header file for FarmBranchAndBound, the master-worker Branch-and-Bound (B&B) on a farm with feedback on an executor of ADS: the master holds the queue of the open nodes, and the workers evaluate and branch the nodes it sends.

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]; the master alone holds the queue Q, out counts the tasks at the workers, and the incumbent \( z \) is shared:

 1  procedure MASTER(R, p)
 2     Q ← R;  out ← 0
 3     loop
 4        DISPATCH()
 5        if out = 0 and (a limit is reached or Q = ∅) then return
 6        receive a task T back from a worker;  out ← out − 1
 7        push the children of T in Q
 8  procedure DISPATCH()
 9     while no limit is reached, out < p and Q ≠ ∅ do
10        if PRUNABLE(the least bound of Q) then
11           the nodes of Q are leaves (pruned);  Q ← ∅;  return
12        T ← the first batch nodes of Q, removed
13        send T to a free worker;  out ← out + 1
14  procedure WORKER(T)                       ▷ on each of the p workers
15     for each n ∈ T do
16        while n ≠ nil do                  ▷ the node, then its dive
17           K ← PROCESS(n);  n ← DIVE(K), unless the node limit is reached
18           add the nodes of K but n to the children of T
19     send T back to the master

The test of line 5 is exact, since the master alone changes Q and every open node is either in Q or in a task that is out; the order of extraction is the one of the selection, and the master only moves nodes, which suits an evaluation that is "expensive" w.r.t. the transfer of a node.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli