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 language | English (US) |
---|---|
Pages (from-to) | 79-102 |
Number of pages | 24 |
Journal | Discrete Optimization |
Volume | 19 |
DOIs | |
State | Published - 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