the parallel B&B by work stealing More...

#include <PBeFS/bnb/StealingBranchAndBound.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
	StealingBranchAndBound (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()]; the node \( i \) goes to the worker \( i \bmod p \)

Detailed Description

template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class PBeFS_di_unipi_it::StealingBranchAndBound< P, Executor >

the parallel B&B by work stealing

Each worker extracts the nodes from its own queue and pushes there the children it generates (with depth-first or plunging, the child that dives is kept), so that a worker goes on in the part of the tree where it is, which is what matters when moving a worker from a node to a distant one costs (e.g., when the evaluator of a worker keeps the changes along the path from the root to its last node). The queues are those of the frontier of work stealing of ADS: the owner of a queue extracts its nodes in the exact order of the selection, with no lock, and a worker whose queue is empty steals about half of the queue of another one, drawn at random, the half that keeps out the best node of the victim. The selection is then best-first within each queue only, and the order of extraction may be farther from the sequential one than that of SharedBranchAndBound. The incumbent is shared, and the search ends when no worker holds a node nor works on one, which the frontier tells; the counter sent of the statistics holds the steals. The nodes have to be copyable with moves that do not throw, since a steal moves them to the thief.