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

David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, Edward C. Sewell

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)79-102
Number of pages24
JournalDiscrete Optimization
Volume19
DOIs
StatePublished - Feb 2016

Keywords

  • Branch-and-bound
  • Cyclic best first search
  • Discrete optimization
  • Integer programming
  • Search strategies
  • Survey

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning'. Together they form a unique fingerprint.

Cite this