#### Introduction

• The Branch and Bound algorithm is a powerful technique for solving optimization problems that has been successfully applied to a wide range of problems.
• Its effectiveness/performance depends on the quality of the bounds used to prune the search space, as well as the problem’s structure of the problem being solved.

#### Definition

• Branch and Bound is a popular algorithmic technique used for solving optimization problems, such as integer programming or combinatorial optimization. The algorithm works by breaking down the problem into smaller sub-problems and solving them one by one in a systematic manner.

#### Characteristics

• The Branch and Bound method is a problem-solving technique used in optimization problems, such as finding the optimal solution to a minimization or maximization problem.
• The Branch and Bound method is particularly useful for problems where the search space is very large or the objective function is difficult to evaluate or an exhaustive search of the entire solution space is not feasible. However, the effectiveness of this method depends on the choice of branching criterion and bound computation, which can be challenging in some cases. By pruning large parts of the search space, the algorithm can find the optimal solution more quickly than a brute-force search.
• Branch and Bound is a widely used algorithmic technique for solving optimization problems, particularly combinatorial optimization problems.
• It involves systematically exploring a tree of subproblems, while keeping track of the best solution found so far, and using this information to prune parts of the search space that cannot possibly contain a better solution.
• In practice, it is often used in conjunction with other techniques, such as dynamic programming or cutting plane methods, to improve its efficiency and effectiveness.

#### Working Principle

• The basic idea behind the Branch and Bound algorithm is to divide the problem into smaller subproblems, each of which is a subset of the original problem. The algorithm then solves each subproblem, and uses the solutions to prune the search space. The algorithm continues this process, dividing the problem into smaller and smaller subproblems until it finds the optimal solution. At each step of the algorithm, a bound is computed for each subproblem, which provides an upper or lower limit on the solution quality. The algorithm uses these bounds to determine which subproblems to explore next. If a subproblem’s bound is worse than the best solution found so far, then the algorithm can prune that subproblem from the search space.
• In other words, the basic idea behind Branch and Bound is to maintain a tree of sub-problems that are generated during the algorithm’s execution. Each node in the tree represents a sub-problem, and the branches of the tree represent the choices that can be made to solve the problem. The algorithm explores the tree in a depth-first or breadth-first fashion, depending on the problem’s characteristics, and maintains a lower bound on the optimal solution found so far.
The algorithm starts by creating the root node of the tree, which represents the original problem. Then, the algorithm generates sub-problems by making decisions, such as fixing a variable or choosing an item, and creates child nodes for each sub-problem. The algorithm then chooses a node to explore, either based on a heuristic or by prioritizing the most promising nodes first.
As the algorithm explores the tree, it keeps track of the lower bound on the optimal solution found so far. Whenever a node’s lower bound exceeds the current best solution’s upper bound, the node is pruned, and the algorithm moves on to explore other nodes. The algorithm terminates when all nodes in the tree have been explored or when a satisfactory solution is found.
• This method works recursively by dividing the problem into smaller sub-problems, or branches, and keeping track of the best solution found so far, or the bound.
• Here’s the summary steps how the Branch and Bound method typically works:
• Step1: Divide the problem into smaller sub-problems, or branches, based on some criterion.
• Step2: Solve each sub-problem using some optimization technique, such as linear programming, dynamic programming, or heuristics.
• Step3: Compute a bound for each sub-problem, which represents an upper or lower limit on the solution value.
• Step4: If the bound for a sub-problem is worse than the best solution found so far, prune that branch and move on to the next sub-problem. Otherwise, continue to recursively divide that sub-problem into smaller branches.
• Step5: Repeat steps 2-4 until all branches have been explored.
• Step6: Select the best solution found among all sub-problems as the optimal solution to the original problem.

#### Examples

• The Traveling Salesman Problem or the Knapsack Problem are common example of Branch & Bound algorithm.

Categories: Algorithm & Design