Branch and Bound

Branch and bound is a method for solving optimization problems by breaking them down into smaller subproblems and using a bounding function to eliminate subproblems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm systematically enumerates candidate solutions by state-space search, with the set of candidate solutions thought of as a rooted tree with the full set at the root; before the candidate solutions of a branch are enumerated, the branch is checked against upper and lower estimated bounds on the optimal solution and is discarded if it cannot produce a better solution than the best one found so far. Algorithms recorded in this atlas are grouped here when their design technique is branch and bound.