FarmBranchAndBound
Declared in bnb/FarmBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class FarmBranchAndBound 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.
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 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
-
inline 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
-
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>