Exact methods: Branch and Bound

This lecture discusses the Branch and Bound algorithm in discrete optimization, which tackles the challenge of exploring a vast set of feasible solutions by dividing it into smaller subsets and selecting the best solution. The algorithm efficiently finds optimal solutions by calculating lower bounds on subsets, avoiding the need to solve all sub-problems exactly. By leveraging these lower bounds, the Branch and Bound algorithm proves optimality without solving every sub-problem, making it particularly useful for large feasible sets. In the context of mixed integer linear problems, lower bounds can be computed by solving the relaxation problem using the simplex algorithm.