DeterministicBranchAndBound
Declared in bnb/DeterministicBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class DeterministicBranchAndBound the parallel B&B by synchronous rounds
At each round the round best open nodes (by the selection of the options, round being the number of workers if 0) are extracted from one queue, and the worker \( i \) evaluates and branches the nodes \( i , i + p , i + 2 p , \ldots \) of the round, in this order, against the incumbent of the start of the round. When all of them are done, the outcomes are merged in the order of the nodes of the round: the feasible values update the incumbent, the children that cannot improve it are pruned, and the others are pushed in the queue. Hence, the nodes evaluated, the incumbent and the bound depend neither on the timing of the workers nor on their number, but only on round, provided that the evaluation of a node by the worker i depends only on the node and on the nodes evaluated by that worker before (which make_worker() allows), and the search can be repeated exactly, as the experiments of a paper need.
The price is the wait of each round for its slowest node, which is small when the evaluation dominates and its time varies little among the nodes; also, a node is evaluated against an incumbent that may be one round old. The node limit is exact, the last round being shortened to it, while the time limit is checked between two rounds and therefore makes the end depend on the timing. A dive is not taken, the plunging selection extracting the nodes by their bound as best-first does.
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 DeterministicBranchAndBound(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>