BranchAndBoundSearch
Declared in bnb/BranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P>
class BranchAndBoundSearch the sequential best-first search with an incumbent
The nodes are extracted by the Selection of the options and evaluated only when they are extracted, a child inheriting until then the bound of its parent or its own estimate, whichever is larger; a node is pruned when it is generated, when it is extracted and after its evaluation, and the search ends when no open node can improve the incumbent by more than the tolerance [see docs/branch-and-bound.md].
Public Types
-
using Value = bb_value_t<P>
the value type
-
using Options = BasicBBOptions<Value>
the options type
-
using SolutionT = BBSolution<Node, Value>
the solution type
Public Functions
-
inline explicit BranchAndBoundSearch(const P &problem, const Options &options = {}, unsigned worker = 0)
constructor, taking the problem (which must outlive the search) and the worker whose evaluator the search uses [see make_worker()], so that sequential searches can run at the same time on different workers
-
inline SolutionT solve(std::vector<Leaf> seeds) const
searches the subtrees of the given nodes, returning the Solution
The nodes (the kind of a BBLeaf is not looked at) are open nodes with their bounds and depths, evaluated only when extracted, e.g., the leaves of a previous search [see BBSolution::frontier] whose bounds are still valid, or set to the unknown bound where they are not; with none, the search ends at once. The bound of the Solution is that of their subtrees, so that the caller combines it with the bounds of whatever nodes it leaves out.
-
using Value = bb_value_t<P>