the parallel B&B with one queue shared by the workers More...

#include <PBeFS/bnb/ParallelBranchAndBound.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
	SharedBranchAndBound (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>
class PBeFS_di_unipi_it::SharedBranchAndBound< P, Executor >

the parallel B&B with one queue shared by the workers

The workers extract the nodes from one queue under a lock, evaluate and branch them outside of it, and push the children back under it (with depth-first or plunging, the child that dives is kept by the worker). The search ends when the queue is empty and no worker holds a node; the open nodes are dropped at once when none of them can improve the incumbent. The order of extraction is close to the sequential one, and the lock is cheap when the evaluation dominates, which is the usual case of a B&B.