bnb/MultiQueueBranchAndBound.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
MultiQueueBranchAndBound	The parallel B&B on the MultiQueue of ADS

Concepts

template<class V>
concept MultiQueueValue

#include <PBeFS/bnb/MultiQueueBranchAndBound.h>

the values that the MultiQueue of ADS takes as keys: arithmetic, with a greatest value, and atomic with no lock

Description of the header

Header file for MultiQueueBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers share the open nodes in the MultiQueue of ADS, a relaxed priority queue of \( 2 p \) sequential queues each under its own lock, as the workers of MQAStar do.

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 that of SharedBranchAndBound [see ParallelBranchAndBound.h] but for the queue and the test of the end: a pop takes the better of the first nodes of two queues drawn at random, and therefore not always the first of all, and the counter \( m \) of the nodes that are in the queue or held by a worker, which is atomic, takes the place of busy and of the lock \( L \):

 1  procedure MULTIQUEUE(R)
 2     Q ← R;  m ← |R|;  done ← false
 3     in parallel, on each worker i = 0, ..., p − 1 do
 4        d ← nil
 5        while not done do
 6           if d ≠ nil then n ← d;  d ← nil
 7           else
 8              n ← a pop of Q, possibly nothing
 9              if no node was popped then
10                 if m = 0 then done ← true else wait a little
11                 continue
12              if PRUNABLE(the bound of n) then
13                 n is a leaf (pruned);  m ← m − 1;  continue
14           if a limit is reached then n is a leaf (open);  done ← true
15           K ← PROCESS(n);  d ← DIVE(K)
16           m ← m + |K| − 1;  push the nodes of K but d in one queue of Q

The test at line 10 is exact: at line 16, \( m \) counts the children and drops the node processed in one atomic step, before the pushes (the child that dives is held by the worker, and counted as such), so that \( m = 0 \) means that \( Q \) is empty and that no worker holds a node, whatever the order of the pops. Since the first node of \( Q \) is not known, a node is pruned when popped (line 12) rather than with all the others, and DIVE compares the children with the bound of the node processed instead of the least bound of \( Q \). The children of a node go into one queue under one lock, as by a stickiness of their number.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli