Searches

headers of the layer bnb

bnb/BranchAndBound.h

Header file for the best-first search with an incumbent, i.e., for Branch-and-Bound (B&B): the concept BranchAndBound of a problem, its options and its Solution, the queue of the open nodes, and the sequential search BranchAndBoundSearch.

Class	Description
BasicEvaluation	The outcome of the evaluation of a node, with values of type V
BBLeaf	A leaf of the tree explored, or a node to start a search from
BBValueTraits	What the B&B needs to know of the type V of its values
BasicBBOptions	The options of a B&B with values of type V
BBStats	The counters of a B&B
BBSolution	The outcome of a B&B
BBQueue	The open nodes of a B&B, ordered by a key
BranchAndBoundSearch	The sequential best-first search with an incumbent

bnb/ParallelBranchAndBound.h

Header file for the parallel best-first searches with an incumbent, i.e., the parallel Branch-and-Bound (B&B) on an executor of ADS (the pool of C++ threads, OpenMP or FastFlow): SharedBranchAndBound, whose workers extract the nodes from one queue as the workers of SPA* do, and DistributedBranchAndBound, whose workers have a queue each and send the children to their owners as the workers of HDA* do.

Class	Description
BasicParallelBBOptions	The options of the parallel B&B with values of type V
BBIncumbent	The incumbent shared by the workers of a parallel B&B
SharedBranchAndBound	The parallel B&B with one queue shared by the workers
DistributedBranchAndBound	The parallel B&B with a queue per worker and the children sent to their owners

bnb/DeterministicBranchAndBound.h

Header file for DeterministicBranchAndBound, the parallel Branch-and-Bound (B&B) by synchronous rounds, whose outcome does not depend on the timing of the workers.

Class	Description
DeterministicBranchAndBound	The parallel B&B by synchronous rounds

bnb/StealingBranchAndBound.h

Header file for StealingBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers keep the children they generate in a queue of their own and take about half of the queue of another worker only when theirs is empty, i.e., by work stealing.

Class	Description
StealingBranchAndBound	The parallel B&B by work stealing

bnb/MultiQueueBranchAndBound.h

Header file for MultiQueueBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers share the open nodes in the MultiQueue of ADS, a relaxed priority queue of $ 2 p $ sequential queues each under its own lock, as the workers of MQAStar do.

Class	Description
MultiQueueBranchAndBound	The parallel B&B on the MultiQueue of ADS

bnb/SelfSplitBranchAndBound.h

Header file for SelfSplitBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers share nothing but the nodes of a first sampling of the tree, as in the SelfSplit of Fischetti, Monaci and Salvagnin (2014).

Class	Description
SelfSplitBranchAndBound	The parallel B&B by a split of the tree after a sampling

bnb/FarmBranchAndBound.h

Header file for FarmBranchAndBound, the master-worker Branch-and-Bound (B&B) on a farm with feedback on an executor of ADS: the master holds the queue of the open nodes, and the workers evaluate and branch the nodes it sends.

Class	Description
FarmBranchAndBound	The master-worker B&B on a farm with feedback

bnb/MPIBranchAndBound.h

Header file for MPIBranchAndBound, the distributed Branch-and-Bound (B&B) with one MPI process per worker: each process has a queue of open nodes and sends the children to their owners, as DistributedBranchAndBound does with threads [see ParallelBranchAndBound.h] and HDAStarMPI with the states of A* [see HDAStarMPI.h].

Class	Description
MPIBranchAndBoundSearch	The distributed B&B with one MPI process per worker