When to apply Branch and Bound Algorithm?

Branch and bound is an effective solution to some problems, which we have already discussed. We’ll discuss all such cases where branching and binding are appropriate in this section.

• It is appropriate to use a branch and bound approach if the given problem is discrete optimization. Discrete optimization refers to problems in which the variables belong to the discrete set. Examples of such problems include 0-1 Integer Programming and Network Flow problems.
• When it comes to combinatory optimization problems, branch and bound work well. An optimization problem is optimized by combinatory optimization by finding its maximum or minimum based on its objective function. The combinatory optimization problems include Boolean Satisfiability and Integer Linear Programming.

Basic Concepts of Branch and Bound:

▸ Generation of a state space tree:

As in the case of backtracking, B&B generates a state space tree to efficiently search the solution space of a given problem instance.

In B&B, all children of an E-node in a state space tree are produced before any live node gets converted in an E-node. Thus, the E-node remains an E-node until i becomes a dead node.

• Evaluation of a candidate solution:

Unlike backtracking, B&B needs additional factors evaluate a candidate solution:

1. A way to assign a bound on the best values of the given criterion functions to each node in a state space tree: It is produced by the addition of further components to the partial solution given by that node.
2. The best values of a given criterion function obtained so far: It describes the upper bound for the maximization problem and the lower bound for the minimization problem.

• A feasible solution is defined by the problem states that satisfy all the given constraints.
• An optimal solution is a feasible solution, which produces the best value of a given objective function.
• Bounding function :

It optimizes the search for a solution vector in the solution space of a given problem instance.

It is a heuristic function that evaluates the lower and upper bounds on the possible solutions at each node. The bound values are used to search the partial solutions leading to an optimal solution. If a node does not produce a solution better than the best solution obtained thus far, then it is abandoned without further exploration.

The algorithm then branches to another path to get a better solution. The desired solution to the problem is the value of the best solution produced so far.

▸ The reasons to dismiss a search path at the current node :

(i) The bound value of the node is lower than the upper bound in the case of the maximization problem and higher than the lower bound in the case of the minimization problem. (i.e. the bound value of the ade is not better than the value of the best solution obtained until that node).

(ii) The node represents infeasible solutions, de violation of the constraints of the problem.

(iii) The node represents a subset of a feasible solution containing a single point. In this case, if the latest solution is better than the best solution obtained so far the best solution is modified to the value of a feasible solution at that node.

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems.

A branch and bound algorithm provide an optimal solution to an NP-Hard problem by exploring the entire search space. Through the exploration of the entire search space, a branch and bound algorithm identify possible candidates for solutions step-by-step.

There are many optimization problems in computer science, many of which have a finite number of the feasible shortest path in a graph or minimum spanning tree that can be solved in polynomial time. Typically, these problems require a worst-case scenario of all possible permutations. The branch and bound algorithm create branches and bounds for the best solution.

In this tutorial, we’ll discuss the branch and bound method in detail.

Different search techniques in branch and bound:

The Branch  algorithms incorporate different search techniques to traverse a state space tree. Different search techniques used in B&B are listed below:

1. LC search
2. BFS
3. DFS

1. LC search (Least Cost Search):

It uses a heuristic cost function to compute the bound values at each node. Nodes are added to the list of live nodes as soon as they get generated.
The node with the least value of a cost function selected as a next E-node.

2.BFS(Breadth First Search):
It is also known as a FIFO search.
It maintains the list of live nodes in first-in-first-out order i.e, in a queue, The live nodes are searched in the FIFO order to make them next E-nodes.

3. DFS (Depth First Search):
It is also known as a LIFO search.
It maintains the list of live nodes in last-in-first-out order i.e. in a stack.

The live nodes are searched in the LIFO order to make them next E-nodes.