So, next general to think was main ideas were going through the stree on a toy example of solving a traveling salesman problem is called the branch-and-bound technique. It is quite similar, actually, to the backtracking technique. But backtracking is usually used for solving decision problems, while the branch-and-bond technique is usually used to solve optimization problems. Its main idea is as follows, again we are going to grow a huge tree which in the end is going to represent the search space. That is the space of all candidate solutions. So, we are going to grow these solutions piece by piece, but It's each step. Instead of doing this naively in each point in this tree, we check whether the current partial solutions that we have, have any chances to be extended to a solution which is better than the one that we currently found. Which is better than the best ones that we've currently seen. If it has no chance, we cut this branch immediately. We do not continue it if we realize that it cannot be extended through a solution which is better than the best one found so far. We illustrate the main idea of the branch-and-bound technique on a toy example. So, consider the following graph consisting of four vertices. The graph is complete, meaning that there is an edge between any pair of vertices. One way to solve this is to consider all possible cycles. For this, we consider the following trees. We start at vertex 1. From vertex 1, we can go to either of the following 3 vertices. Go to vertex 2, go to vertex 3 or go to vertex 4, right? From the vertex 2, we are allowed to go right at the vertez 3 or to vertex 4. We are not allowed to go back to vertex 1 because we need a cycle that treated each vertex exactly one. And so, what I am trying to extend each possible partial solution with each possible variant. So, from vertex 3 we actually need to go to vertex 4, and from vertex 4 we have no choice but to return to vertex 1. So, when we see that this is a full cycle visit and each vertex exactly 1, we computer its total length. So, in this case it is 19. And we do this for all possible cases. Here we have 7, here we have 18, here we have 7 again, 18 again, and 19 again. So, we have actually pairs of equals numbers here because the corresponding leaves. For example, this leaf and this leaf, they actually correspond to the same cycle, but reversed in two different directions. We can either go this way or this way. This leaf actually is the same cycle, of course, but, with the same total lengths. Now, let's do it in a more smart way. Let's grow the same three but, let's try to compute the total lengths of total partial, or current partial solution on the fly, instead of computing this at the leaf. Namely, initially we stay at the vertex 1. So, the total length is 0, then we go, for example to the vertex 2. At this point the total length is 1. From vertex 1 we, from vertex 2, we try to go vertex 3. This gives us total length safes. So, this is our current as we go from 1 to 2 and then from 2 to 3. The current total length is 6. We then try to go vertex 4, this is only actually possibility, so our total lengths is 9 and then we return back to the vertex 1 because we already visited all other vertices. So, this is the first full cycle that we discovered, so we start the length is 19, so we marked that the best total length that we've seen so far is 19. Then we go back, then we backtrack actually to consider as a possibilities. The last vertex on our pass, when there were some possibilities, is the vertex 2. Instead of going to vertex 3, we might want to go to vertex 4. This gives us the total of the current length is 3. Then we continue on now is the current length is 6. And finally, when we get to the leaf of this tree, we see that the current cycle give us gives us total length 7, so we update our variable which is responsible for the best solution found so far it is 7, okay. Then again we backtrack. Now the last vertex where there is still a possibility to go to another vertex is the root of this tree. So, we tried to go from 1 to vertex 3 but not to 2. So, the line says the current solution is 1. Then we, from 3 we go to 6, from 6 we go to 4. And now we see that the lengths of the total of the current partial solution is always greater. So, 8 is greater than 7. So, out current solution is not going to be extended to some scene which is better than some scenes that we found so far. So, there is no sense to extend the current branch puzzle. So, we just go back, so we return back to this vertex and we try to go from 3 to another vertex, namely to 4. Then when we go to 4, we discover another copy of the same cycle, so its length is 7. Then it doesn't update our variable, so we just backtrack. We go to the root and we try to visit the vertex 4. But already when we go from 1 to 4 we see that we already traversed the edge of length 10, right. The length of this partial solution is already 10. It is already worse than the solution that we found before of total length 7. So, there is just no sense of extending this branch and we cut it immediately. So, if we do this a little bit smarter, then we do not need to go through all possible candidates solutions. So this is the one small branch that we cut. And this is another small branch that we don't need. So, in general it can save a lot of time. In our example now a toy, example we consider it probably is the most simple lower bound for estimating the size of any extension of a partial solution. So, modern on TSP-solvers that I able to handle graphs with thousands of vertices. Use smarter heuristics for lower bounding and optimal solution in a given graph. We provide two examples which are still simple enough and not so smart that's used instead of. So, the first lower bound says that in any graph the total length of any traveling salesman cycle is at least the following expression, one half times the sum over all vertices where for each vertex we compute the sum of two edges of minimum distance adjacent to this vertex. Well, why is that? Well, if we just consider an optimal cycle. Note that if we just consider edges in this cycle, then the total length of this cycle just equals to this expression. Where instead of two minimal length edges for each vertex, we used just two edges that are adjacent to it, right? Just because in this expression each edge in the sum this edge is counted exactly twice, for example this edge is going to be counted one time, once for this vertex once for this vertex, for this reason we have one one half here. So, if you we just use instead of two adjacent edges in an optimal cycle we use two edges of minimum lengths in the initial graph. This is obviously the lower bound for the lengths of an optimal cycle. And it can already be a good results and practice. And as a lower bound is that in any graph with non negative edge lengths, the total lengths of an optimal cycle, is at least the length the minimum spanning tree. Why is that? Well, this is just because if you have an optimal, An optimal cycle, and then you remove some edge from it, then what you get is a path in this tree. And this path use a spanning tree in this graph right. So, but it is not the minimum spanning, probably not the minimum spanning trees, so the weight of this part is at least the weight of the minimum spanning tree which means that the length of the cycles is at least the weight of our spanning tree. So, this concludes our module our lesson on exact algorithms. In the next lesson, we are going to consider approximate algorithms. So, these are algorithms that worked in polynomial and written solutions which might not be optimal. But they are guaranteed to be close to optimal.