Branch and Bound Applications - TSP using MST bounds
So, I was having trouble figuring out how to do branch and bound using MST but I figured it out. To understand it, should know Kruskal’s algo for MSTs and a basic understanding what the Travelling Salesman(TSP) problem is. So here’s an example:
Given this graph, apply Branch and Bound Method using MST-based bounding scheme to solve the TSP. Use DFS starting from A and search alphabetically.
So basically, first you start with A in your search tree and you add B to it. Now we say that you have a partial solution $[a, S, b]$ where $S$ is all the nodes in your current path including $a$ and $b$. $a$ and $b$ are your start and end nodes so far. We say the graph is $G=(V,E)$.
Now your lower bound using the MST scheme consists of the sum of: the lightest edge from your start node $a$ (in this case A) to the rest of the nodes $V-S$ + the lightest edge from your end node $b$ (here it’s B) to $V-S$ + the MST (easy with Kruskal’s) of $V-S$ + the cost of the path so far.
So here we have:
Continue on until this lower bound exceeds the lowest best value so far for a complete TSP path. The solution is as follows: