DistributedBranchAndBound
Declared in bnb/ParallelBranchAndBound.h; the same class on the site of Doxygen.
-
template<BranchAndBound P, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class DistributedBranchAndBound the parallel B&B with a queue per worker and the children sent to their owners
Each worker extracts the nodes from its own queue, and sends each child, in batches, to the worker that owns it: \( \mathrm{hash}( n ) \bmod p \) if the problem gives hash( n ), a random worker otherwise (with depth-first or plunging, the child that dives is kept). Since a tree has no duplicates, the owners only balance the load. The incumbent is shared, and the termination is detected as in HDAStar, by the mailbox of ADS.
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 DistributedBranchAndBound(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()]; each node goes to its owner, which is the worker \( i \bmod p \) for the node \( i \) if the problem gives no hash( n )
-
struct Msg
a node travelling to its owner
-
using Value = bb_value_t<P>