the parallel B&B on the MultiQueue of ADS More...

#include <PBeFS/bnb/MultiQueueBranchAndBound.h>

Public Types
using	Node = typename P::node_type
	the node type
using	Value = bb_value_t< P >
	the value type
using	Options = BasicParallelBBOptions< Value >
	the options
using	Leaf = BBLeaf< Node , Value >
	the leaf type
using	SolutionT = BBSolution< Node , Value >
	the solution type

Public Member Functions
	MultiQueueBranchAndBound (const P &problem, const Options &options={})
	constructor, taking the problem (which must outlive the search)
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
SolutionT	solve (void) const
	searches the tree from the root, returning the Solution
SolutionT	solve (std::vector< Leaf > seeds) const
	searches the subtrees of the given nodes, returning the Solution [see BranchAndBoundSearch::solve()]

Detailed Description

template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
requires MultiQueueValue< bb_value_t< P > >
class PBeFS_di_unipi_it::MultiQueueBranchAndBound< P, Executor >

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.