# Dynamic Programming vs Branch and Bound

Dynamic Programming vs Branch and Bound is discussed in this blog post. Both methods are used for solving optimization problems. Optimization methods find the best solution out of a pool of feasible solutions. The aim of optimization methods is to minimize or maximize the given cost function.

Branch and Bound is a method for solving discrete and combinatorial optimization issues as well as mathematical optimization problems. The collection of candidate solutions is viewed as forming a rooted tree with the entire set at the root in a branch-and-bound method, which uses state-space search to systematically enumerate them. The method investigates the tree’s branches, which are subsets of the solution set. Before enumerating a branch’s candidate solutions, it’s tested against upper and lower estimated bounds on the optimal solution, and it’s eliminated if it can’t generate a better solution than the algorithm’s best so far.

Dynamic programming is a computer programming approach as well as a mathematical optimization tool. Richard Bellman invented the approach in the 1950s, and it has since been used in a variety of industries. It refers to breaking down a big problem into simpler sub-problems in a recursive way in both situations. While certain choice issues cannot be deconstructed in this manner, decisions that span many points in time are frequently dismantled in this manner. In computer science, a problem is said to have optimum substructure if it can be solved optimally by breaking it down into sub-problems and then recursively finding the best solutions to the sub-problems.

## Dynamic Programming vs Branch and Bound

Dynamic Programing |
Branch and Bound |

Constructs the solution in form of a table. | Constructs the solution in form of a tree. |

Solves all possible instances of problem of size n. | Only solves promising instances from the set of instances at any given point. |

Does not require a bounding function. | Needs to compute and apply a bounding function at each node. |

After constructing the table, it needs to be traced back to find the solution sequence. | The solution sequence is implicit, a leaf node of the tree is the final solution. |

Applications: Binomial Coefficient Making a change Knapsack problem Multistage graph optimal Binary Search Tree Matrix Chain Multiplication Longest Common Subsequence Bellman-Ford (SSSP) Algorithm Assembly Line Scheduling Traveling Salesman Problem Flow Shop Scheduling |
Applications: Traveling salesman problem Knapsack problem Job Sequencing Problem |

Additional Reading: Read More