MultiQueueBranchAndBound
Declared in bnb/MultiQueueBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class MultiQueueBranchAndBound the parallel B&B on the MultiQueue of ADS
The workers pop the nodes from the MultiQueue of ADS, evaluate and branch them, and push the children into one of its queues under one lock (with depth-first or plunging, the child that dives is kept by the worker); no lock is shared by all the workers, and two of them wait for each other only when they draw the same queue. The order of extraction is relaxed: a pop takes a node whose rank among the open ones is less than \( \frac{5}{6} \cdot 2 p \) in expectation, and the nodes of equal key come out in no given order. The search ends when the atomic counter of the nodes in the queue or held by a worker falls to 0 [see the pseudocode above]. The values have to be arithmetic and atomic with no lock [see MultiQueueValue], since the least key of each queue is read with no lock, and the nodes default constructible, since the buffers of the queues are arrays.
Public Types
-
using Value = bb_value_t<P>
the value type
-
using Options = BasicParallelBBOptions<Value>
the options
-
using SolutionT = BBSolution<Node, Value>
the solution type
Public Functions
-
inline explicit MultiQueueBranchAndBound(const P &problem, const Options &options = {})
constructor, taking the problem (which must outlive the search)
-
inline void set_executor(Executor &ex) noexcept
sets the Executor that runs the workers, which must outlive the searches; without it, each search builds one of as many threads as there are workers
-
inline SolutionT solve(std::vector<Leaf> seeds) const
searches the subtrees of the given nodes, returning the Solution [see BranchAndBoundSearch::solve()]
-
using Value = bb_value_t<P>