StealingBranchAndBound
Declared in bnb/StealingBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class StealingBranchAndBound 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.
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 StealingBranchAndBound(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()]; the node \( i \) goes to the worker \( i \bmod p \)
-
using Value = bb_value_t<P>