# 9.4 Branch and Bound

Branch-and-Bound is a powerful technique that has become one of the most widely used methods in operations research and computer science for solving complex combinatorial optimization problems. These types of problems are ubiquitous, and are found in many different fields such as logistics, manufacturing, transportation, and scheduling. They are characterized by having a finite set of possible solutions, among which we must find the best one.

The Branch-and-Bound algorithm is particularly efficient in solving these types of problems because it strategically navigates the space of potential solutions, discarding suboptimal solutions along the way, which saves us from having to exhaustively enumerate and evaluate all possibilities. This approach is especially useful when the number of possible solutions is very large, as in many real-world applications.

The basic idea behind the Branch-and-Bound algorithm is to divide the problem into smaller sub-problems, and recursively...