Home »
Algorithms
Branch and Bound
In this article, we will learn about the concept of branch and bounding.
Submitted by Shivangi Jain, on July 17, 2018
Branch and bound
- Branch and bound is a state space search method that can be termed as an improved form of backtracking.
- It is suitable for solving the combinatorial optimization problem.
- These problems have an enumerable finite feasible solution.
-
In this approach, a set of feasible solutions are partitioned and the subsets that do not have an optimal solution are deleted for further consideration. Thus, the branch and bound has two major steps:
- Branching
- Bounding
The following are the steps that are repeated to solve any problem are:
1) Branching
Branching is the first step of the branch and bound technique. This technique involves division of the main problem into two or more subproblems. These subproblems are exclusive and independent of each other. In addition, they are similar to the original problem but smaller in size i.e. the operation applied to the main problem can also be applied to these subproblems.
2) Bounding
Bounding operation restricts the state space tree to grow exponentially.
Branch and bound is the extension of backtracking which is used to solve combinatorial optimize problem. This is more useful because in this the branches are more optimally find as it uses the breath first search so, that our search is more optimal and state space tree is more compact. This can be solved by using the following:
- FIFO - (First In First Out): The list of live nodes is a first - in - first - out the list. Example - queue.
- LIFO - (Last In Last Out): The list of the live nodes is a last - in - first - out the list. Example - stack.
- LCS - (Least Cost Search): In this, we give the preference to an answer node with minimum cost.
The branch and bound is that state space method in which all the children’s of the E-node are generated before any other live node can become the E-node. The two graph strategies i.e. the Breath first search and depth-first search, in which the exploration of a new node cannot begin until the node currently being explored is fully explored. Bounding function is used to avoid the generation of subtrees that do not contain an answer node. Branch and bound check the state space tree complexity for an optimal value and potential solutions are always obtained. This branch and bound is mostly used as it makes more compact state space tree.