Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning

By David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, Edward C. Sewell. Discrete Optimization, 2016

565 citations recorded by the source corpus.

The branch-and-bound (B&B) algorithmic framework has been used successfully to find exact solutions for a wide array of optimization problems. B&B uses a tree search strategy to implicitly enumerate all possible solutions to a given problem, applying pruning rules to eliminate regions of the search space that cannot lead to a better solution. There are three algorithmic components in B&B that can be specified by the user to fine-tune the behavior of the algorithm. These components are the search strategy, the branching strategy, and the pruning rules. This survey presents a description of recent research advances in the design of B&B algorithms, particularly with regards to these three components. Moreover, three future research directions are provided in order to motivate further exploration in these areas.

Subfields: Artificial Intelligence, Computer Networks and Communications, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/415209fa7a01e1ca4a64d13c3e0810b57dc910f4