0:10

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.

Â 1:41

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.

Â 2:58

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.

Â 3:54

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.

Â 6:39

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

Â 7:33

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,

Â 8:48

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.

Â