BranchAndBoundSearch< P > Class Template Reference

the sequential best-first search with an incumbent More...

#include <PBeFS/bnb/BranchAndBound.h>

Public Types
using	Node = typename P::node_type
	the node type
using	Value = bb_value_t< P >
	the value type
using	Options = BasicBBOptions< Value >
	the options type
using	Leaf = BBLeaf< Node , Value >
	the leaf type
using	SolutionT = BBSolution< Node , Value >
	the solution type

Public Member Functions
	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
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

Detailed Description

template<BranchAndBound P>
class PBeFS_di_unipi_it::BranchAndBoundSearch< P >

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].

Member Typedef Documentation

Leaf

template<BranchAndBound P>

using Leaf = BBLeaf< Node , Value >

the leaf type

Node

template<BranchAndBound P>

using Node = typename P::node_type

the node type

Options

template<BranchAndBound P>

using Options = BasicBBOptions< Value >

the options type

SolutionT

template<BranchAndBound P>

using SolutionT = BBSolution< Node , Value >

the solution type

Value

template<BranchAndBound P>

using Value = bb_value_t< P >

the value type

Constructor & Destructor Documentation

BranchAndBoundSearch()

template<BranchAndBound P>

BranchAndBoundSearch ( const P & problem, const Options & options = {}, unsigned worker = 0 )

inlineexplicit

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

Member Function Documentation

solve() [1/2]

template<BranchAndBound P>

SolutionT solve ( std::vector< Leaf > seeds ) const

inlinenodiscard

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.

solve() [2/2]

template<BranchAndBound P>

SolutionT solve ( void ) const

inlinenodiscard

searches the tree from the root, returning the Solution

---

The documentation for this class was generated from the following file:

• PBeFS/bnb/BranchAndBound.h