StealingBranchAndBound.h File Reference

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

#include <atomic>
#include <cstdint>
#include <memory>
#include <optional>
#include <utility>
#include <vector>
#include "PBeFS/bnb/ParallelBranchAndBound.h"
#include "ADS/concurrent/StealablePriorityQueue.h"

Go to the source code of this file.

Classes
class	StealingBranchAndBound< P, Executor >
	the parallel B&B by work stealing More...

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

Detailed Description

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