bnb/StealingBranchAndBound.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
StealingBranchAndBound	The parallel B&B by work stealing

Description of the header

Header file for StealingBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers keep the children they generate in a queue of their own and take about half of the queue of another worker only when theirs is empty, i.e., by work stealing.

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]; each worker \( i \) has a queue \( Q_i \) in the frontier of work stealing of ADS:

 1  procedure STEALING(R)
 2     the k-th node of R in Q_(k mod p)
 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(i);  if n = nil then return
 8           if a limit is reached then
 9              n is a leaf (open);  stop all the workers;  return
10           K ← PROCESS(n)
11           d ← DIVE(K);  push the nodes of K but d in Q_i
12  procedure NEXT(i)
13     if Q_i ≠ ∅ and PRUNABLE(the least bound of Q_i) then
14        the nodes of Q_i are leaves (pruned);  Q_i ← ∅
15     if Q_i ≠ ∅ then return the first node of Q_i, removed
16     loop
17        if stopped, or no worker holds a node or works on one, return nil
18        v ← a worker ≠ i at random
19        if Q_v holds two nodes at least then
20           move about half of them, but the first, to Q_i
21           if some were moved, return the first node of Q_i, removed
22        wait a little

Lines 15 to 22 are the extraction of the frontier, whose test of the end at line 17 counts the workers that hold a node or work on one and the thieves that are trying a steal, and is therefore exact; the owner of a queue extracts from it with no lock, and a thief waits for the next operation of the victim, i.e., at most the evaluation of a node. A worker steals only when its own queue is empty (line 16), and therefore it stays in its own part of the tree; the selection is then best-first within each queue only.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli