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.