The Branch and Bound technique allows to solve the TSP instances exactly in practice. That is where the Branch and Bound algorithm is guaranteed to output the best, that is optimal, solution. The only issue is that it is not guaranteed to have a low running time. That is, on some instances it is quick, on some instances it is slow. Its main idea is the following, assume that we were just enumerating all possible cycles of all possible permutations. How would we do this? So we start with some node, then we know that from this node we can go to either this node, or that node, or that node. So N minus one of the nodes. From each of these nodes, we can go to either this one, or this one, or this one. So we construct what is recursively these three or four permutations. At the same time, for some branches of the tree, we can cut them somewhere in the middle, just because we already know that this branch, or this current subpath, cannot be extended to an optimal solution. And this is best illustrated with an example. So just consider this small graph with four nodes and this is how the whole tree of all permutation looks like. So from the node, we start with node one, okay? From one, we can go to either two, three or four, okay? From the node two, we can go either to three or four just because we did not go to one because one is already visited. Similarly, from node three we can go either to two or to four, okay? From the node four we can go to either two or three, again, because one is already visited, okay? Then from three, we have already no choice, we need to go to four, and, then, to go back to one, and so on. So the leaves of this tree correspond to all possible permutations, and actually, from all possible permutations starting with one. And you see that seven is the best length of a cycle, so the best cycle in this case is, let me draw it on our point example, going from one to two, from two to four, from four to three, and from three to one, right? Which gives us a cycle of length seven. And we see that there is another cycle of length seven, and, essentially, this is the same cycle but traverse in another direction. So, since here we have a nondirected graph, so every cycle will appear twice in our recursive tree, okay? And now comes the idea of pruning this search tree, and this is actually the essence of the Branch and Bound technique. Let's do the following, let's construct this recursion tree just node by node, okay? So we start at node number zero, so we, when we just state, node number one, I'm sorry. When we just state node number one, so the length of the current subpath is equal to zero, because we haven't yet traversed any edge. Then from node number one, we can go to node number two, and at this point the length of current path is equal to one because we already traversed this edge of length one, okay? From two, we go to three, and the length of the current path is equal to six. So this is just because, this is just one plus five. So we obtain the lengths of the current subpaths. Finally, from three, the only available node is four, so we go four, and then we come back to one. And then, we save the information that we already see in the cycle of lengths, 19, okay? So we save it in a variable call, something like best so far. So this is a very useful information, and we will use it in order to cut some of the branches in our tree. Now, let's get back to the nearest node where there was some choice, and this is this node actually, because, from two, we might as well go to the node four. So let's try to go to the node four. So this gives us the subpaths. So this subpath in the initial graph it corresponds to this one, and it has length three, okay? From four, we go to three, and then we have no choice again. So we come back to the node one and now we see that this leads us to a better cycle of length seven. And we save it in our variable best so far. Okay, this actually means that if we are extending some path, and we see that its length is already greater than seven, then there is just no sense in extending it further, right? Because we already have a cycle of length seven, and we are interested in a shorter such cycle. So let's get back to where we started. And let's try from the first node to go to the third node, okay? We go from one to three, then we go from three to two, then from two to four. And now we see that this path is already too long, so there is no sense in extending it. But, actually, we do not save anything at this point because, well, we already traversed all the nodes. But then, let's consider what happens in another branch. Well, in another branch, we again find this cycle of length seven. But then, in the final branch, if from the first node we go to the fourth node, then we see that, in this case, there is no sense of, like, extending further the subtree, because already going from zero to the node four gives us a path which longer than the best cycle that we've seen so far, right? So, definitely, if we use this very heavy edge, we're not going to extend it to a cycle which is going to be shorter than seven, right? So using this very simple idea we were able to cut some of the branches. So for this point example the savings are modest, of course, but when the graph is larger and there is a larger deviation in the edge weight, the savings might be very dramatic. Okay? So once again, what we used to lower bound the length of the cycles that we can get in the current branch is almost something trivial, right? So we use the following fact, if the length of the current subpath is too long, then it definitely cannot be extended to something which is better than the optimal one, right? If it is already the longest and optimal, then by adding some edges would not make it less than optimal, right? And this is basically, the whole approach is used in some of the very efficient state-of-the-art TSP-solvers. However, the heuristics of the methods for lower bound is that all the extensions of the current class used in this solvers are much trickier. Let me just mention two of such methods which are still simple enough, and in practice, much more complicated things are used. Imagine that we have a graph, and we would like to compute weekly some lower bound on the length of the optimal TSP cycle in this graph. That was it. First, the first approach tells us that we can compute the following quantity. So for every node in this graph, we will take two incident edges, assume for simplicity that the graph is undirected. Then, we just take two edges of minimum weight that are adjacent to this node. So, we compute the sum of all such edges for all the nodes, and we take one half of them. So I claimed that this gives us a lower bound for the optimal TSP cycle. So why is that? Well, just because in a TSP cycle, for every node, we have to use two adjacent edges. For example, for this node, will be this edge and this edge. So for every node, we need to use two adjacent edges, and the sum of the weights of these two adjacent edges are definitely at least, the sum of two minimum weight edges adjacent to this node. So this is a clear lower bound. So, the only things that should be clarified is that, why we have this one half here? This is just because when computing all these minimum edges for all the nodes, some of the edges can be computed twice. For example, this node might be the minimum adjacent edge to this node and to that node. And since we computed it twice to make this lower bound to work, we need to take the half of the sum of all these edges. So, this is a quantity that can be computed very quickly, very efficiently, and this already gives us a lower bound. If we see that this lower bound is already greater than the best solution that we've seen so far, then we stop immediately and cut the current branch. Another way of lower bounding the optimal cycle is the following: So assume that we have a graph, and we can strike the minimum spanning tree in this graph. Assume that the graph is undirected also, then what I claim is that the weight of this minimum spanning tree is at most the weight of the traveling salesman person cycle. Why is that? Well, again, let's consider an optimal traveling salesman person cycle. Let me just denote its weight just by TSP. Now, let me do the following. Let me just remove some edge. Then what we know is that since all the edge weights are not negative, we know that what is left has weight smaller than the traveling salesman person cycle. And also, as you can see from this picture, what we get is some spanning tree. This is just a plot, but this is a special case of a tree. It spans all the nodes, and it has n minus one edges. So, what we know is that TSP is at least the weight of this particular tree. And this tree, this is a spanning tree. Let me write it. The weight of this spanning tree is definitely at least, the weight of the minimum spanning tree because the weight of the minimum spanning tree is the smallest one. And this finally proves that the weight of the optimal TSP cycle is at least the weight of the minimum spanning tree. And as you probably remember, the minimum spanning tree can be computed very efficiently almost in linear time. So it is quite easy to compute minimum spanning tree, and even for graphs with thousands of edges. It can be computed just in a greedy fashion. We keep taking edges one by one starting from the lightest one. Now let me summarize. So the branch and bound technique. It consists, actually, of two methods. The first one is how we enumerate all the nodes that are going to be visited after the current one. In our example, we considered just some random order. When implementing this idea, it makes sense to stick to some particular heuristic. For example, a reasonable choice like going to the next node is to go to the nearest next node. So, if we went from one to two, and then we are choosing the next node to go, then it makes sense to start probably not with node number three but with node number five, if the edge from two to five is shorter than the edge from two to three. So it makes sense to enumerate nodes to visit the next nodes in order of the increasing distance from the current node. The next heuristic used inside the branch and bound algorithm is how we lower bound the cycle in the remaining graph. So, we've used another 20 examples, we used a very simple one. And then, we've discussed through slightly more complicated ways of measuring. From this way of measuring, we need the following three things. First, it is efficiently computable. We would like to compute this lower bound very quickly, and on the other hand, it should be a lower bound, it should be a quantity such that the traveling salesman person cycle is at least this quantity. So, as we've discussed already, this is guaranteed to find an optimal solution, because we are essentially enumerating all possible cycles, and we cut only the branches where we were absolutely sure that there is no optimal cycle, because the cycles that we're going to find in this branch is definitely longer than some cycles that we've seen before. The running time of this idea actually it depends on the instance itself and the two heuristic used. So, the smarter is the heuristic, the better is the running time usually. At the same time, if the heuristic works, if the heuristic of lower bounding, for example, is too slow, this can be a trade-off. So sometimes, a heuristic gives a good lower bound but it is too slow, for example, so there is some trade-off. So finally, let me mention that this is exactly the idea that is used in modern TSP-solvers that are actually able to solve instances of the traveling salesman person problem, consisting of thousands of nodes.
