SelfSplitBranchAndBound
Declared in bnb/SelfSplitBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class SelfSplitBranchAndBound 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.
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 SelfSplitBranchAndBound(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>