Branch-and-bound

The same machinery runs a best-first search with an incumbent, i.e., a Branch-and-Bound (B&B), on a problem satisfying the concept BranchAndBound of BranchAndBound.h. Such a problem gives a copyable node_type, a sense (minimization or maximization), the root node, and two methods: evaluate( n ) returns the bound of the node n, whether it is infeasible and possibly a feasible value, while branch( n , sink ) gives the children of n, each with a bound that is cheap to compute. Alternatively, make_worker( i ) gives each worker an evaluator of its own (e.g., with a copy of a model and of a solver), which may also take the incumbent value by cutoff( z ) before each evaluation (e.g., to stop a relaxation that cannot improve it). Note that a B&B tree has no duplicates; hence, there is no closed list. A node is evaluated only when it is extracted, which pays off when the bound is “expensive” (say, a Linear Program), and it is pruned when it is generated, when it is extracted and after its evaluation. Also, the nodes can be extracted best-first, depth-first, breadth-first, by an estimate of the problem, or by plunging (a dive into the best child, then best-first). The search ends when no open node can improve the incumbent beyond an absolute or relative tolerance (usually well before the queue is empty); it reports the bound and the gap also when a node or time limit stops it. On request, the Solution also holds the leaves of the tree explored, and a search can start from any set of nodes instead of the root, which allows one to reoptimize after a change of the data that leaves the branching valid, or to resume a search stopped by a limit.

The search is sequential (branch_and_bound( p , options )), parallel with a queue shared by the workers as in SPA* (SharedBranchAndBound) or with a queue per worker and the children sent to their owners as in HDA* (DistributedBranchAndBound), master-worker on a farm with feedback (FarmBranchAndBound), all of them on the three runtimes, with one MPI process per worker (MPIBranchAndBoundSearch, whose nodes travel as bytes), or by synchronous rounds (DeterministicBranchAndBound), whose outcome depends neither on the timing of the workers nor on their number, as the deterministic mode of FiberSCIP [18], so that the experiments of a paper can be repeated exactly, or by the SelfSplit of Fischetti, Monaci and Salvagnin [19] (SelfSplitBranchAndBound), whose workers search apart, and without exchanging anything, the subtrees of a first sampling of the tree, which ends with a dive to a leaf so that they start from an incumbent, the outcome depending then only on the number of the workers (or, sharing their incumbent, pruning more at the price of that determinism), or by work stealing [20] (StealingBranchAndBound), whose workers keep the children they generate and take about half of the queue of another worker [36] only when theirs is empty, so that each worker stays in its own part of the tree, which pays when moving the evaluator of a worker to a distant node is costly, or on the MultiQueue of ADS (MultiQueueBranchAndBound), the queue of MQA*, whose workers share the open nodes with no lock common to all of them, at the price of a relaxed order of extraction. The searches that need no external library can also be chosen by a value, or by its name read from a file of parameters (parallel_branch_and_bound( p , bb_scheme( "selfsplit" ) , options )), so that a program built on the library gets every new scheme with no change of its own. In the taxonomy of Gendron and Crainic [16], all of them build one tree in parallel (their type 2), asynchronously but for the rounds, with a single pool of open nodes (the shared queue, the MultiQueue, the farm and the rounds) or with a pool per worker (the distributed queues, the work stealing, the SelfSplit and MPI); the parallelism inside a node (their type 1) is left to the evaluation of the problem, and the search of several trees at once (their type 3) is not provided. SafePBNF and PA*SE have no counterpart, since they exist to handle duplicates and re-expansions, which a tree does not have; for the same reason, the owner of a node only balances the load. Its design is discussed in docs/branch-and-bound.md, and the tests check the variants on the 0-1 knapsack against the dynamic program.