What is a Branch and Bound Algorithm?

For combinatorial, discrete, and general mathematical optimization problems, branch and bound algorithms are employed to discover the best solution. A huge diversity of optimization problems, such as production planning and crew scheduling, are classified as NP-Hard because they cannot be answered in polynomial time. The branch-and-bound (B&B) algorithm is a frequently used technique for obtaining exact solutions to NP-hard optimization problems. The method, which was first developed by Land and Doig, is frequently called an algorithm; though, it is more accurate to say that B&B contains a family of algorithms that all share a common primary solution procedure.

Because it uses the state space tree, it is similar to backtracking. The Branch and Bound is not a solution strategy that is merely relevant to integer programming problems. Instead, it is a problem-solving strategy that can be used to solve a variety of issues.

The B&B’s Basic concept

A branch and bound method enumerate all possible candidate solutions in a stepwise manner by searching the whole search space. We start by creating a rooted decision tree with all of the feasible outcomes. The entire search space is represented by the root node:

Here each child node is a portion of the solution set and is a partial solution. We determine an upper and lower constraint for a given problem based on the optimal solution before constructing the rooted decision tree. At each level, we must decide which nodes should be included in the solution set. We investigate the node with the best bound at each level to quickly locate the best and most optimal solution.

In such instances, it is now critical to establish a good upper and lower bound. Any local optimization approach or picking any point in the search space can be used to obtain an upper bound. Convex relaxation or duality, on the other hand, can provide a lower bound. In general, we wish to break down the solution set into smaller subsets. Then, at each level, we choose the best feasible subset (node) to obtain the best possible solution set using a rooted decision tree.

Solving Optimization Problems with B&B

Branch and Bound algorithm is the backbone of mixed-integer programming and one of the most widely used algorithms in optimization. So, first, let’s begin with what an optimization problem is, which can be summed up as:

In this equation, we wish to minimize the function f (also called the cost function) by x from the set X. The set X could be a collection of all real numbers, a collection of integers, or something else entirely… It’s also possible that there’s a collection with real-number and integer vectors in it. The important thing to keep in mind is that X represents the range of choices. As a result, we only need to worry about the solutions that result from this set.

The branch and the bound algorithm have an easy concept. Given specific subsets of X, it discovers the boundaries of the cost function f. It is based on the optimization bounding principle, which is essentially a fancy phrase for a fairly basic concept.

Principle of Branch and Bound Method

The fundamental idea of the branch and bound technique is that a large number of plausible solutions can be broken down into smaller subsets, which can then be analyzed to find the optimal option. When solving an integer programming issue, a branch and bound strategy are utilized in conjunction with the traditional non-integer solution approach. In general, when a viable integer solution is formed at a node and the upper bound at that node is larger than or equal to the upper bound at any other ending node, the optimal integer solution is reached.

Stages of Branch and Bound Algorithm

The following are the stages in the branch and bound approach for getting an optimal integer solution for a maximization model (with ≤ constraints):

1. With the integer limitations relaxed, look for the best solution to the linear programming model.
2. Set the relaxed solution to act as the upper bound and the rounded-down integer solution to act as the lower bound at node 1.
3. For branching, choose the variable with the largest fractional component. Build two new constraints for this variable that represent the integer values that have been partitioned. As a result, a new constraint ≤ and a new constraint ≥ will be created.
4. Make two nodes, one for the ≥ constraint and the other for the ≤ constraint.
5. At each node, the upper bound represents the relaxed solution whereas, the lower bound is the existing maximum integer solution (at any node).
6. If the method generates a viable integer solution with the highest upper bound value of any ending node, it means that the optimal integer solution has been found.
7. If there isn’t a possible integer solution, branch from the node with the highest upper bound.
8. Go back to the 3rd step.

When to use Branch and Bound Algorithm?

The supervised learning algorithm commonly employs this approach. Which uses a tree structure to choose the best subset of features. All features say n, are included in the root node. The intermediate children nodes have one less characteristic than their parent node and the sequence is followed until the leaf nodes are reached. Once the size of the feature subset has been determined, say x, the tree can be built using x features in the leaf nodes. The criterion value for a leaf node is evaluated and set as a bound value, b, after it has been attained. If the criterion value of another branch exceeds b, then b is upgraded to it, and that branch is stretched to its leaf nodes. If the criterion value is less than b, the branch is skipped. The leaf node with the greatest criterion value is chosen in the end.

Bounding Function

The bounding function is a crucial element of any Branch and Bound algorithm in the sense that a low-quality bounding function cannot be substituted by effective dividing and selection techniques. The value of a bounding function for a certain subproblem should ideally match the value of the best viable solution to the problem, but as finding this value is typically NP-hard, the aim is to get as near as possible with as little computational work as possible (i.e. in polynomial time). Strong bounding functions create values that are close to the optimum for the bounded subproblem, while weak bounding functions produce values that are distant from the optimal.