TY - JOUR
T1 - Branch-and-bound algorithms
T2 - A survey of recent advances in searching, branching, and pruning
AU - Morrison, David R.
AU - Jacobson, Sheldon H.
AU - Sauppe, Jason J.
AU - Sewell, Edward C.
N1 - Funding Information:
This research has been supported in part by the Air Force Office of Scientific Research ( FA9550-10-1-0387 ), the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (32 CFR 168a), and the National Science Foundation Graduate Research Fellowship Program (DGE-1144245). Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, the United States Air Force, the Department of Defense, or the United States Government. The majority of this work was completed while the first and third authors were Ph.D. students at the University of Illinois at Urbana–Champaign.
PY - 2016/2
Y1 - 2016/2
N2 - 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.
AB - 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.
KW - Branch-and-bound
KW - Cyclic best first search
KW - Discrete optimization
KW - Integer programming
KW - Search strategies
KW - Survey
UR - http://www.scopus.com/inward/record.url?scp=84958225554&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958225554&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2016.01.005
DO - 10.1016/j.disopt.2016.01.005
M3 - Article
AN - SCOPUS:84958225554
VL - 19
SP - 79
EP - 102
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
ER -