MPIBranchAndBoundSearch
Declared in bnb/MPIBranchAndBound.h; the same class on the site of Doxygen.
-
template<MPIBranchAndBound P>
class MPIBranchAndBoundSearch the distributed B&B with one MPI process per worker
Each process extracts the nodes from its own queue, and sends each child, in batches and with non-blocking sends, to the process that owns it: \( \mathrm{hash}( n ) \bmod p \) if the problem gives hash( n ), a random process otherwise (with depth-first or plunging, the child that dives is kept). A process that improves the incumbent sends its value to all the others, and calls the callback of the options; the node of the incumbent stays on it until the end, when it is sent to all. The end is detected with the four-counter method of Mattern by the mailbox of ADS, a process joining a wave when it has no node that can improve the incumbent and no batch to send. The node limit is split evenly among the processes; a process that reaches its share, or the time limit, stops the mailbox of all the processes, and the nodes left open, those still travelling included, bound the optimum.
MPI must be initialized by the caller, with at least MPI_THREAD_FUNNELED if the problem uses threads; all the processes of the communicator call solve(), and all of them get the same Solution, but for the frontier [see BBSolution], each process keeping the leaves that it owns. Started from given nodes, each process starts from its own ones, and these leaves can be given back to the same process for a later search.
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 MPIBranchAndBoundSearch( )
constructor, taking the problem (which must outlive the search), the options (threads is ignored) and the communicator
-
inline SolutionT solve(void) const
searches the tree from the root, returning the Solution (on every process)
-
inline SolutionT solve(std::vector<Leaf> seeds) const
searches the subtrees of the given nodes of this process, returning the Solution (on every process) [see BranchAndBoundSearch::solve()]
-
using Value = bb_value_t<P>