Branch and Bound

Intro to Branch and Bound :

Branch and bound is a systematic method for solving optimization problems
B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.

Uses of Branch and Bound :

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems. In general, given an NP-Hard problem, a branch and bound algorithm explores the entire search space of possible solutions and provides an optimal solution.

Algorithm :

Set L = {X} and initial ize x
2  while L # 0 :
3   Select a subproblem S from L to explore
4   if a solution.r' E {x E S I f (x) < /(x)} can be found: Set .X =x'
s   if S cannot be pmned:
6   Partition S imo S1 , S2 , ... , S,. Insert S1, S2, . . . , S, into L
8   Remove S from L
9 Return x

conclusion :

cutting planes can reduce the search space and thus improve the lower bounds on solutions of mixed integer linear programs. When using cutting planes, the branch-and-bound algorithm is also called the branch-and-cut algorithm. Preprocessing can reduce problem size and improve problem solvability.