GENERAL METHOD OF BRANCH AND BOUND
Introduction :
Branch and bounds are basically an algorithm that is used to get the correct method of the solution for the use of the discrete, combination, and general mathematical problems that need to be optimized.
The branch and bound algorithm basically explores the amount of entire space for the search of the possible solutions and it then provides an optimal solution.
This algorithm consists of a step-wise enumerate approximate possible solutions by exploring the search space entirely. So basically all the possible solutions that build at first get a rooted decision tree.
If the problem that is given is discrete in a manner for the optimization problem then the branch and bound is a better choice. The discrete optimization is the subpart of the optimization where the variables in that particular problem should belong to that discrete set.
The algorithm branch and bound work efficiently on the combination optimization problems. It looks actually for the best solution to be provided for a particular problem in that entire space of the solution.
The bounds that are in the function that needs to be optimized are actually merged with that value of the latest best solution. It basically allows that algorithm to find the parts of the solution space totally.
Purpose :
To provide and maintain the lowest cost paths to the concerned target. Once the solution is found it just keeps improving that solution. Branch and bound algorithms are implemented in deep bounded search and depth-first search.
We can control the quality of the solution that is expected even if the solution is not yet found or introduced into that algorithm. This algorithm basically applies to those complex problems that have a finite number of solutions, in which those solutions can get represented as a particular sequence of options. The first portion of the branch and bound requires many choices that will branch out into the solution space in order to get the finite solutions.
Advantages :
- In the algorithm of branch and bound it doesn’t explore the nodes in that tree. Therefore the complexity of time of the algorithm of branch and bound is less as time-consuming compared to other algorithms.
- If in such a case the given problem is not very large and if it is possible to do the branching of the nodes in a reasonable amount of time, then it finds an approximate optimal solution for that particular problem.
- The algorithm of branch and bound get a minimal path in order to reach the optimal solution for that particular problem. Therefore it does not keep on repeating nodes while it explores the tree.
Disadvantages :
- This branch and bound algorithm are mostly time consuming. It depends on the size of that particular problem and the number of particular nodes in that given tree can be too large in its worst case.
- Secondly, the process of parallelization is also too difficult in that bound and branch algorithm.
Reference