bnb

The tree searches of branch-and-bound, sequential and parallel, and their choice by scheme.

Headers of the layer

Header	Description
bnb.h	Tree searches of PBeFS, i.e., the best-first searches with an incumbent (Branch-and-Bound) of a problem satisfying the concept BranchAndBound, save the one that needs MPI, MPIBranchAndBound.h.

Searches

Header	Description
bnb/BranchAndBound.h	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.
bnb/ParallelBranchAndBound.h	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.
bnb/DeterministicBranchAndBound.h	The parallel B&B by synchronous rounds
bnb/StealingBranchAndBound.h	The parallel B&B by work stealing
bnb/MultiQueueBranchAndBound.h	The parallel B&B on the MultiQueue of ADS
bnb/SelfSplitBranchAndBound.h	The parallel B&B by a split of the tree after a sampling
bnb/FarmBranchAndBound.h	The master-worker B&B on a farm with feedback
bnb/MPIBranchAndBound.h	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].

Schemes

Header	Description
bnb/BranchAndBoundScheme.h	Choice of the Branch-and-Bound (B&B) by its scheme: BBScheme names the searches of the core of PBeFS, bb_scheme() reads it from its name (e.g., from a file of parameters), and parallel_branch_and_bound() runs the search of the scheme of the options on a runtime, so that a caller chooses the search by a value rather than by a type.

Problems

Header	Description
bnb/Knapsack.h	Struct template BasicKnapsack, a 0-1 knapsack problem that implements the BranchAndBound concept [see BranchAndBound.h] with values of a given type, and Knapsack, the one with values of type double, with the random instances of the classes of Pisinger and the dynamic program that gives their optimal value; the tests and the benchmark of the Branch-and-Bound share it.

Documentation

Page	Description
Branch-and-bound as best-first search	The incumbent, the bounds, the pruning and the selection rules, and A* as a special case.
Parallel branch-and-bound	The shared, distributed, master-worker, deterministic, SelfSplit, stealing and MultiQueue schemes: correctness, termination and determinism.
Best-first search with an incumbent: design note	The extension of the searches to branch-and-bound: the concept, the sequential and the parallel searches, the reoptimization.