dmeoli / PBeFS / 39129514859

95%

push

github

Branch-and-bound: the best-first search with an incumbent, sequential and parallel on the runtimes of the library

BranchAndBound.h gives the concept of a problem (root(), evaluate( n ),
branch( n , sink ), or make_worker( i ) for a worker of its own), the
options, the Solution with the bound and the gap, the queue of the open
nodes and BranchAndBoundSearch; ParallelBranchAndBound.h gives
SharedBranchAndBound (one queue, as in SPA*) and DistributedBranchAndBound
(a queue per worker and owners, with the termination of HDA*), on the C++
threads, OpenMP and FastFlow. The nodes are evaluated when extracted, with
pruning at generation, at extraction and after the evaluation, the
selections best-first, depth-first, best-estimate and plunging, and an
absolute or relative tolerance. The cases bb and bb-* of the tester check
them on the 0-1 knapsack against the dynamic program.

499 of 517 new or added lines in 2 files covered. (96.52%)

2319 of 2498 relevant lines covered (92.83%)

39174537.68 hits per line