the parallel B&B by a split of the tree after a sampling More...

#include <PBeFS/bnb/SelfSplitBranchAndBound.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
	SelfSplitBranchAndBound (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::SelfSplitBranchAndBound< P, Executor >

the parallel B&B by a split of the tree after a sampling

The tree is first explored sequentially (the sampling), by the selection of the options and without dives, until the open nodes are split per worker (4 if 0) or the tree is solved. The open nodes are then extracted in the order of the selection, the \( k \)-th going to the worker \( k \bmod p \), and each worker searches the subtrees of its nodes sequentially [see BranchAndBoundSearch], with its own evaluator, its own incumbent (starting from that of the sampling, which with split_dive ends with a dive to a leaf) and its share of the node limit. The Solution has the best incumbent of the workers (that of the lowest worker among equal values), the least of their bounds, and their leaves and counters together with those of the sampling.

The workers neither share the incumbent nor exchange nodes, and therefore the outcome depends only on split and on the number p of the workers, provided that the evaluation of a node by a worker depends only on the node and on the nodes that worker evaluated before; the sampling is done once, by the evaluator of the worker 0. The price is the balance of the load, which is that of the subtrees of the split, and an incumbent found by a worker that does not prune the nodes of the others. With split_shared the workers prune also by the best incumbent of all of them, read at each extraction, at the price of the determinism: the value is still the optimum, but the nodes evaluated, and the node of the optimum among equal values, depend on the timing. As in the deterministic search, the time limit makes the end depend on the timing.