the master-worker B&B on a farm with feedback More...

#include <PBeFS/bnb/FarmBranchAndBound.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
	FarmBranchAndBound (const P &problem, const Options &options={})
	constructor, taking the problem (which must outlive the search); threads is the number of workers, batch the nodes per task
void	set_executor (Executor &ex) noexcept
	sets the Executor that runs the master and the workers, which must outlive the searches and have at least threads + 1 threads; without it, each search builds one of threads + 1 threads
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::FarmBranchAndBound< P, Executor >

the master-worker B&B on a farm with feedback

The master extracts the nodes from its queue by the Selection and sends them, batch at a time, to the workers that are free; a worker evaluates and branches each node, offering its feasible value to the shared incumbent, and sends back the children that survive the pruning (with depth-first or plunging, it goes on with the child that dives in the same task). The search ends when the queue is empty, or no node of it can improve the incumbent, and no task is out at a worker. Since the master only moves nodes, the order of extraction is the one of the selection, and the scheme suits an evaluation that is expensive w.r.t. the transfer of a node.

The farm runs threads + 1 threads, those of an Executor of ADS [see ADS::feedbackFarm()]: with PBEFS_PIN the master takes the first CPU of the affinity mask and the worker \( i \) the CPU \( i + 1 \) of it, counting from 0 [see pin_worker()], but for the thread of the caller.