the parallel B&B by synchronous rounds More...

#include <PBeFS/bnb/DeterministicBranchAndBound.h>

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

Public Member Functions
	DeterministicBranchAndBound (const P &problem, const Options &options={})
	constructor, taking the problem (which must outlive the search)
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
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 [see BranchAndBoundSearch::solve()]

Detailed Description

template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class PBeFS_di_unipi_it::DeterministicBranchAndBound< P, Executor >

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.