Branch and Bound

An exact search that partitions the solution space into a tree of subproblems and, at each node, computes a bound (a limit on the best value that branch can reach) to prune any branch that cannot beat the incumbent — the stronger the bound, the more of the tree it cuts. It is the backbone of exact methods for cutting & packing such as 2D Bin Packing, and combined with column generation it becomes branch-and-price for integer programs with many variables.