Branch & Bound: Optimization

This lecture covers the Branch & Bound algorithm, a divide and conquer approach to explore feasible solutions efficiently by using bounds on the optimal cost. The algorithm iteratively partitions the problem into subproblems, computes lower and upper bounds, and prunes infeasible solutions. LP-based Branch & Bound is discussed, along with examples demonstrating the algorithm's application. The lecture also delves into the Pigeonhole Problem, LP relaxation, and portfolio optimization, emphasizing the trade-off between risk and return. Additionally, it explores Nonlinear Programming, the Fermat-Weber Problem, and the Ball Circumscription Problem.