DeterministicBranchAndBound.h File Reference

Header file for DeterministicBranchAndBound, the parallel Branch-and-Bound (B&B) by synchronous rounds, whose outcome does not depend on the timing of the workers. More...

#include <algorithm>
#include <barrier>
#include <exception>
#include <mutex>
#include <optional>
#include <utility>
#include <vector>
#include "PBeFS/bnb/ParallelBranchAndBound.h"

Go to the source code of this file.

Classes
class	DeterministicBranchAndBound< P, Executor >
	the parallel B&B by synchronous rounds More...

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

Detailed Description

Header file for DeterministicBranchAndBound, the parallel Branch-and-Bound (B&B) by synchronous rounds, whose outcome does not depend on the timing of the workers.

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 and the procedures PROCESS and PRUNABLE of the sequential search [see BranchAndBound.h], which a worker runs here with the incumbent \( z_0 \) of the start of the round and with an incumbent of its node alone; \( r \) is the number of nodes of a round (round, \( p \) if 0), and the procedure NEXTROUND is run by one worker while the others wait at a barrier:

 1  procedure DETERMINISTIC(R)
 2     Q ← R;  z ← the given incumbent, or ∞;  N ← ()
 3     in parallel, on each worker i = 0, ..., p − 1 do
 4        loop
 5           barrier, at which one worker runs NEXTROUND()
 6           if done then return
 7           for j = i, i + p, i + 2p, ... while j < |N| do
 8              (K_j, v_j) ← PROCESS(N_j) against z₀, v_j being the best
                   feasible value of N_j below z₀, if any
 9  procedure NEXTROUND()
10     for j = 0, ..., |N| − 1 do                  ▷ in the order of N
11        if v_j < z then z ← v_j;  N_j is the node of z
12        for each m ∈ K_j do
13           if PRUNABLE(β(m)) then m is a leaf (pruned) else push m in Q
14     if a limit is reached, Q = ∅ or PRUNABLE(the least bound of Q) then
15        done ← true;  return
16     N ← the first min(r, evaluations left) nodes of Q, removed
17     z₀ ← z

The nodes of a round, their order and the incumbent \( z_0 \) against which they are evaluated are fixed before the round starts (lines 16 and 17), and the outcomes are merged in the order of the nodes (line 10); hence, the nodes evaluated, the incumbent and the bound depend only on \( r \), and neither on the timing nor on the number of the workers, provided that the evaluation of a node by the worker \( i \) depends only on the node and on the nodes evaluated by \( i \) before. The node limit is exact (line 16), while the time limit, checked at line 14, makes the end depend on the timing; no dive is taken.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli