Branch And Bound
Branch and Bound is an algorithmic technique used for solving optimization problems, particularly in operations research and computer science. It systematically explores the solution space by dividing it into smaller subproblems, or "branches," and evaluating their potential to find the best solution. Each branch is assessed using bounds to eliminate those that cannot yield better results than the current best.
The method involves two main components: branching, which creates subproblems, and bounding, which calculates upper or lower limits on the possible solutions. This approach helps in efficiently narrowing down the search, making it suitable for problems like traveling salesman and knapsack.