Q7Design and Analysis of Algorithms

Branch and Bound is an algorithm design technique for solving discrete optimization problems. It exhaustively searches the solution space while using bounding functions to eliminate (prune) subspaces that cannot contain the optimal solution, thereby avoiding unnecessary exploration.

Three key steps: (1) Branch — divide the problem into subproblems (branch the search tree); (2) Bound — compute an optimistic bound (upper/lower) on the best solution achievable in each subspace; (3) Prune — discard branches where the bound is worse than the current best solution. Used for TSP, 0/1 Knapsack, and Integer Programming.