bnb/FarmBranchAndBound.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
FarmBranchAndBound	The master-worker B&B on a farm with feedback

Description of the header

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