MPIBranchAndBoundSearch< P > Class Template Reference

the distributed B&B with one MPI process per worker More...

#include <PBeFS/bnb/MPIBranchAndBound.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
	MPIBranchAndBoundSearch (const P &problem, const Options &options={}, MPI_Comm comm=MPI_COMM_WORLD)
	constructor, taking the problem (which must outlive the search), the options (threads is ignored) and the communicator
SolutionT	solve (void) const
	searches the tree from the root, returning the Solution (on every process)
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()]

Detailed Description

template<MPIBranchAndBound P>
class PBeFS_di_unipi_it::MPIBranchAndBoundSearch< P >

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.

Member Typedef Documentation

Leaf

template<MPIBranchAndBound P>

using Leaf = BBLeaf< Node , Value >

the leaf type

Node

template<MPIBranchAndBound P>

using Node = typename P::node_type

the node type

Options

template<MPIBranchAndBound P>

using Options = BasicParallelBBOptions< Value >

the options

SolutionT

template<MPIBranchAndBound P>

using SolutionT = BBSolution< Node , Value >

the solution type

Value

template<MPIBranchAndBound P>

using Value = bb_value_t< P >

the value type

Constructor & Destructor Documentation

MPIBranchAndBoundSearch()

template<MPIBranchAndBound P>

MPIBranchAndBoundSearch ( const P & problem, const Options & options = {}, MPI_Comm comm = MPI_COMM_WORLD )

inlineexplicit

constructor, taking the problem (which must outlive the search), the options (threads is ignored) and the communicator

Member Function Documentation

solve() [1/2]

template<MPIBranchAndBound P>

SolutionT solve ( std::vector< Leaf > seeds ) const

inlinenodiscard

searches the subtrees of the given nodes of this process, returning the Solution (on every process) [see BranchAndBoundSearch::solve()]

solve() [2/2]

template<MPIBranchAndBound P>

SolutionT solve ( void ) const

inlinenodiscard

searches the tree from the root, returning the Solution (on every process)

---

The documentation for this class was generated from the following file:

• PBeFS/bnb/MPIBranchAndBound.h