# Practice English Speaking&Listening with: Lec-24 Traveling Salesman Problem(TSP)

Normal
(0)
Difficulty: 0

In this lecture, we discuss the Travelling Salesman Problem. The Travelling Salesman

Problem is an extremely important problem in operations research. We first define the

problem and then we look at methods or algorithms to solve the Travelling Salesman Problem.

Later, we will also discuss the relevance and importance of Travelling Salesman Problem

in the OR literature. What is a Travelling Salesman Problem?

Let us look at a situation where there are five cities or five nodes. Let us say that

there is a person who is right now in node 1. Now, this person has to visit each of the

remaining nodes once and only once and come back to the starting point. The person may

choose to start from 1 and from 1 to go to 2 and say from there to 4, to 5, then to 3

and back to 1 is one feasible solution to the Travelling Salesman Problem. Alternately,

another feasible solution could be it goes through 1 to 4, 4 to 3, 3 to 2, 2 to 5 and

5 to 1. Any permutation or order in which the person starts from a particular node,

in this case, the given node goes to every other node or vertex once and only once and

comes back to the starting point is called the Travelling Salesman Problem and particularly

to find out that tour or circuit, which gives minimum distance travelled or minimum cost

travelled. The problem is: Given a network, given a set

of points to visit every node once and only once and come back to the starting point,

travelling minimum distance or incurring minimum cost. This is called the Travelling Salesman

Problem as it is. In a five city Travelling Salesman Problem, if we assume that the person

starts with 1, let us say, a feasible solution could be 1 to 5, 5 to 2, 2 to 3, 3 to 4 and

4 to 1. We also realize that this solution is the same as 2 to 3, 3 to 4, 4 to 1, 1 to

5 and 5 to 2. So, effectively, in a Travelling Salesman Problem, it does not matter which

city or which node the travelling salesman starts. The only thing is, from any node the

person can start, but the person has to visit every other node once and only once and come

back to the starting node. There are n nodes; we realize that there are

n minus 1 factorial feasible solutions, because corresponding to this solution, which say

the 1 5 2 3 4 1 is the same as 5 2 3 4 1 5 which is the same as to 2 3 4 1 5 2 and so

on. Because each of these n factorial solutions have five solutions that repeat we have n

minus 1 factorial feasible solution to the Travelling Salesman Problem. The question

is to find out among these n minus 1 factorial feasible solutions, the one with the best

value or the minimum distance value. This problem also comes from graph theory.

In graph theory, there is a famous problem of finding out whether a graph is Hamiltonian.

If we look at a graph like this, a graph is a collection of nodes and arcs that we saw

earlier as part of these. If we look at a graph like this with three nodes and three

arcs, it is possible to find a sub graph which is 1 3 2 1, which means from 1, I go through

every vertex once and only once and I come back. So, this is Hamiltonian. Whereas, if

we have the same graph like this, then starting from 1, I can go to 3, 4 but then, I have

to come back to 3 and then come to 2 and to 1. So, this graph is not Hamiltonian.

One of the interesting decision problems in graph theory is if the given graph is Hamiltonian.

So, given a graph, the decision problem from graph theory is to find out whether it is

Hamiltonian. When we say whether it is Hamiltonian, we say whether there is a Hamiltonian circuit

which means I start from this point. If you take this particular graph, this graph is

Hamiltonian 1 to 2, 2 to 3, 3 to 4 and 4 to 1. So, it has a Hamiltonian circuit. I could

do 1 to 2, 2 to 3, 3 to 4 and 4 to 1 which is the same as 1 to 4, 4 to 3, 3 to 2 and

2 to 1. If I add this also into this graph, I may do 1 2 3 4 1; I may do 1 2 4 3 1 and

so on. If a graph is Hamiltonian it may have more than one Hamiltonian circuit. From graph

theory we also have graphs which are completely connected graphs.

If we have a graph here where every vertex is connected to every other vertex then clearly this graph is Hamiltonian.

You could do 1 2 3 4 5 1; you could do any of these n factorial possibilities. If somebody

is given a graph like this and if the decision problem is posed whether this graph is Hamiltonian,

then the decision problem is easy to answer because with every vertex is connected to

every other vertex, the graph has to be Hamiltonian. In such a case, the decision problems move

on to an optimization problem where we try to find out, given this graph is Hamiltonian

and it has more than one Hamiltonian circuit, can we find the least cost Hamiltonian circuit?

Now, that leads us to a Travelling Salesman Problem wherein we find out the least cost

Hamiltonian circuit in a given graph, knowing that that graph is Hamiltonian. In a TSP we

normally assume that it is possible to go from every city to every other city. Usually,

the distance data in a Travelling Salesman Problem will look like this.

This is for a typical five city Travelling Salesman Problem where all these represent

the costs or the distances. For example, to go from 1 to 3 it is 8, to go from 1 to 4

it is 9 and so on. We also observe that we do not have a situation, where we say here

that I cannot go from 3 to 4. Usually in a TSP, it is assumed that you can go from every

city to every other city. The only other difference is the cost or distance between a node and

itself should ordinarily be 0, but we do not put a 0 here. We simply put a dash here whenever

we solve a Travelling Salesman Problem where this dash represents, infinity.

Later, we will explain why we have replaced the 0 with the dash, but, otherwise, in a

TSP every node is connected to every other node by arcs. This means the graph is complete,

which also means, that Hamiltonian circuit exists. If every node is connected to every

other node, then n minus 1 factorial Hamiltonian circuit are possible and feasible. The Travelling

Salesman Problem is to find out that among the n minus 1 factorial, which has the least

total cost or the least total distance. We have already said from this figure that we

could have a feasible solution 1 to 2, 2 to 4, 4 to 5, 5 to 3, 3 to 1 or we could do 2

to 5, 5 to 1, 1 to 4, 4 to 3, 3 to 2. These are all feasible solutions.

If we look at something like this, I go from 1 to 2, I go from 2 to 3, come back from 3

to 1; go from 4 to 5 and 5 to 4 is not feasible to the Travelling Salesman Problem. These

are called subtours and we should not have subtours. We should have only a full tour

where we would have 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 to 1, which means, I visit every

city once and only once and I come back to the starting point. The travelling salesman

feasible solution should comprise of tours and should not comprise of subtours. Before

we get into solving the Travelling Salesman Problem let us first try and formulate the

TSP. Very quickly, we will look at two types of formulations of a TSP.

One is we define Xij equal to 1, if the person goes immediately from i to j. The objective

function is to minimize the total distance travelled. This will be double sigma Cij Xij.

We have already seen that this Cij could represent a cost or it would represent a distance. If

we look at a 5 by 5, given by this data, the person has to leave from every city. So, we

will have sigma Xij for j equal to 1 to n equal to 1 summed over all i. This means,

if I am in city I, I have to go to some other city j and I go to only 1 out of the remaining

cities. That is taken care of by summation j equal to 1 to n, from i, it is equal to

1 for every i. The other one is sigma Xij equal to 1, i equal

to 1 to n for every j. This means, if I am in a particular city at the moment, I should

have come from only one of the cities into the present city that I am right now in. That

is given by Xij equal to 1 summed from i equal to 1 to n for every j; we also know that Xij

is 0 or 1. I immediately go from i to j or I do not go from i to j.

So far, the formulation of the Travelling Salesman Problem appears to be like that of

the more familiar assignment problem. If you look at it carefully, the assignment problem

has exactly this formulation. The only difference, of course, is because of unimodularity; we

put Xij greater than or equal to 0. In a TSP, we do not have that; so, we need to add some

more constraints into the Travelling Salesman Problem. Those constraints are called subtour

elimination constraints.

What are these subtour elimination constraints? If I have, say, five cities; if I get into

a solution like this, where I have, say this is 1 and 5, X15 equal to 1 and X51equal to

1. Now, this is a subtour. We should not have subtours of this type. If we have a five city

TSP, we could have a subtour of length 1, that is, you may have Xjj equal to 1, which

is called subtour of length 1; this is subtour of length 2 and something like this is subtour

of length 3; we could have subtour of length 4 and so on. We could have subtours of several

lengths starting from 1 to n minus 1 if we are looking at an n city Travelling Salesman

Problem and each of these subtours should be eliminated.

One of the ways of doing this is to eliminate subtours of length 1 by simply putting Xjj

equal to 0, so that I do not have a solution that has X11 equal to 1 or X22 equal to 1.

So, I will not have something like this, . That is one way of doing it, explicitly. The other

way of doing is to declare the distance between the point and itself to infinity, represented

by a dash, so that it does not come into the solution. That is precisely, the reason, why

we have the dashes coming here instead of the 0s. Otherwise, we would always have diagonal

assignments with 0s being here. We will have diagonal assignments; we do not want diagonal

assignment because diagonal assignment represents subtour of length 1. We eliminate subtours

of length 1, not by explicitly putting Xjj equal to 0, but by putting Cjj equal to infinity.

The cost associated with the diagonals are all infinity, so that we do not have subtours

of length 1. We want to eliminate subtours of length 2. We need to add a constraint like

this type Xij plus Xji is less than or equal to 1. What does this constraint do? If we

look at specifically this pair, this would mean, if this subtour exists then X15 equal

to 1 and X51equal to 1, which means Xij plus Xji should be equal to 2. The moment we add

this constraint, then this will make sure that this situation does not happen.

If X15 is in the solution, then X51cannot be in the solution. If X51 is in the solution

then X15 will not be in the solution. We can have a situation where both of them are not

in the solution. Therefore, this is a good way by which we eliminate subtours of length

2. Similarly, subtours of length 3 can be eliminated by Xij plus Xjk plus Xki is less

than or equal to 2, which would eliminate subtours of length 3, which means, we will

not have this situation. If for example, this is 1, this is 5, this is 2, this is 4 and

this is 3, then if X12 equal to 1 and 2, 4 equal to 1, X41 cannot be equal to 1; otherwise,

it will violate this constraint. Any general subtour elimination constraint

can be written like this: if we want to eliminate subtours of length k, then we can put Xij

up to k terms, is less than or equal to k minus 1. That is another way to start doing

the subtour elimination constraints. If there are n nodes then we have superscript n C2

constraints here because this is done for every pair. We have superscript n C3 here

because we are eliminating subtours of length 3 and then superscript n C4, superscript n

C5 and so on. One of the problems in the travelling salesman formulation is that the subtour elimination

constraints are large and many. If we are looking at n equal to 5, then superscript

n C2 is 10, superscript n C3 is equal to superscript n C2 which is also 10. Whereas, if you are

looking at a twenty city problem, then superscript n C2 will be 20 into 19 by 2, which is 190

constraints and so on. The Travelling Salesman Problem belongs to

a class of problems where we have a large number of constraints and typically exponentially

increasing number of constraints, because any superscript n Cr can be treated as exponential.

It has a large number of constraints associated with this particular problem. The next issue

that happens is can we still reduce the number of constraints from this particular number?

Let us go back and look at the same example that we have.

We have to eliminate subtours of length 1, subtours of length 2, subtours of length 3

and subtours of length 4. We are solving a five city Travelling Salesman Problem. If

we were solving a ten city problem, then we have to eliminate 1, 2, 3, and 4, up to 9.

We have already eliminated subtours of length 1 by putting Cjj equal to infinity. We should

eliminate subtours of length 2 by adding this constraint, which is a superscript n C2 constraint

that we add now. How do we eliminate subtours of length 3? If there is a subtour of length

3 and there are five cities, there has to be another subtour. You cannot have a situation

where there is only one subtour; if there is a subtour, then, there has to be another

subtour. There will be more than one subtour if you have it.

If there is a subtour of length 3, then there should be subtours of length 2 or length 1,

so that the 5 is taken care of. For every subtour of length 3, there has to be another

subtour, at least one more subtour, which is either a subtour of length 1 or subtour

of length 2. By eliminating subtours of lengths 1 and 2, we automatically eliminate subtours

of length 3. Similarly, if we have a subtour of length 4, then there has to be a subtour

of length 1. So, by eliminating all subtours of length 1, we automatically eliminate subtours

of length 4. For a five city problem, it is enough to eliminate subtours of length 1 and

2. Do not worry about 3 and 4. Already 1 is eliminated by this way, so we only add superscript

n C2 constraints in a five city TSP. In a seven city TSP, we will have to eliminate

subtours of length 1, 2 and 3 because 4, 5, 6 and 7, we can eliminate by carefully eliminating

1, 2 and 3. 1 is always eliminated by this, so for a seven city, we need to add superscript

n C2 plus superscript n C3. When n is an odd number, then the number of constraints that

we will add is superscript n C2 plus superscript n C3 and so on up to superscript n Cn minus

1 by 2. So this many constraints we add if n is odd. If n is even then, let us say we

have six cities. We should eliminate subtours of length 1, 2, 3, 4 and 5. We eliminate this

by putting Cjj equal to infinity; this you do by superscript n C2. You have to do this

again by doing this superscript n C3, then you can go back and say for every subtour

of length 4, we should have subtours of lengths 2 and 1. So, by eliminating these two, we

have eliminated this and by eliminating this, we eliminate this. So, when n is even, we

end up doing superscript n C2 plus superscript n C3 plus etc., plus superscript n Cn by 2.

This way we actually reduce the number of constraints here. When we first formulated,

we said we have to do n C1, n C2, n C3 and up to n Cn minus one. We realize by carefully

looking at the problem: if n is odd, it is enough to go up to superscript n Cn minus

1 by 2; if n is even, go up to superscript n Cn by 2. The number of constraints to a

Travelling Salesman Problem is still very large and usually Travelling Salesman Problems

are not solved directly by integer programming and by formulating it this way. This is only

to understand the Travelling Salesman Problem represents a class of problems where the number

of constraints in a particular type of formulation, the number of constraints is large exponential

and it increases with increase in the number of nodes. Much later, people came up with

a very interesting form of a subtour elimination constraint and we will look at it that way.

Instead of explicitly avoiding subtours of length 2, 3, etc., up to n minus 1, this kind

of a constraint was used. We simply said Ui minus Uj plus nXij is less than or equal to

n minus 1, for i is equal to 1 to n minus 1 and for j equal to 2 to n. Effectively,

this has about n square constraints or n minus 1 square constraints about n square constraints,

because i is equal to 1 to n minus 1, j is equal 2 to n. How do these constraints work?

We have also introduced Ui and Uj, so n more variables into the formulation. Let us see

how this constraint works.

Let us take a situation where we have a subtour 1 2 3 1 and 4 5 4 for a TSP that is a five

city problem. Let us say I have 1 2 3 1 and I have 4 5 1 to 2, 2 to 3, 3 to 1, 4 to 5,

5 to 4. If we have this kind of a constraint, then let us try and apply this now. Ui minus

Uj minus nXij is less than or equal to n minus 1. Ordinarily, we will have U1 minus U2 minus

5X12 is less than or equal to 4. For 2 to 3, I will have U2 minus U3 plus 5X23 is less

than or equal to 4. It is plus 5X23 in the first statement. Then, it is not defined for

j equal to 1, so I do not have the third constraint. I do not have a third constraint which says

U3 minus U1 plus 5X31 less than or equal to 4. I have only two constraints because it

is not defined for j equal to 1. When I add vertically, I will get U1 minus U3 plus 10

is less than or equal to 8. Assuming that this is equal to 1 and this is equal to 1

it is always possible to define U1 and U3 such that this constraint is satisfied. Therefore,

when we consider a subtour involving 1, we are unable to see that this is a subtour elimination

constraint. But, in fact, it is a subtour elimination constraint because for every subtour

that involves city 1, there will be a subtour that does not involve city 1. This means because

this subtour involves city 1, this subtour does not involves city 1.

What are the corresponding equations here? This is U4 minus U5 plus 5 is less than or

equal 4 and U5 minus U4 plus 5 less than or equal to 4. Adding these two, 10 is less than

or equal to 8. For the subtour that does not involve 1, this is a subtour elimination constraint

because we cannot define values for any U4 and U5. We will end up getting 10 less or

equal to 8, which will violate this particular constraint. So, this will become a subtour

elimination constraint for every subtour that does not involve 1. We also know that for

every subtour that does not involve 1, there is a subtour that involves 1; therefore, that

also gets eliminated. So this becomes a very valid subtour elimination constraint for every

subtour, but we also have to show that this is valid for every tour.

A tour should have 1. So, if we have a tour which is 1 2 4 3 5 1, then we have U1 minus

U2 plus 5 is less or equal to 4; U2 minus U4 plus 5 less than or equal to 4; U4 minus

U3 plus 5 less than or equal to 4; U3 minus U5 plus 5 less than or equal to 4 and it is

not defined for 1. When we add vertically, you will get U1 minus U5 plus 20 is less than

or equal to 16. It is always possible to find U1 and U5 such that this is satisfied.

Every tour will satisfy this, so this will not eliminate a tour. This will eliminate

only a subtour and it will eliminate all subtours. This becomes a very valid subtour elimination

constraint for the Travelling Salesman Problem. This, with fewer than n square constraints

makes it a little easier from the formulation point of view because otherwise we were looking

at superscript n C2 plus superscript n C3 plus up to superscript n Cn by 2, which is

a much larger number than n square. This kind of a substitution has been used extensively

by people who actually formulated the TSP as an integer programming problem. There are

also further refinements to this from the literature, some of which have made it slightly

more elegant with respect to this formulation. Nevertheless, we also as mentioned earlier

we do not solve the Travelling Salesman Problem optimally by using this integer programming

formulation. It becomes extremely cumbersome. Travelling Salesman Problems are solved to

exactness or to optimality normally by using branch and bound algorithms that provide exact solution

to the Travelling Salesman Problem. We also know that branch and bound algorithms are

all worse case exponential, in the sense, they do not guarantee polynomial running time.

We could get into situations where we consume a large amount of CPU time before we terminate

or we could have situations where we do not terminate at all. They are solved using branch

and bound algorithms to begin with; and sometimes, we resort to heuristic algorithm which are

fast, but which do not guarantee exactness or exact solutions.

We now see different versions of branch and bound algorithm to solve the Travelling Salesman

Problem. Later, we also see some heuristic solutions to the Travelling Salesman Problem.

So, we will first look at the branch and bound solution for this sum. Let us look at a branch

and bound 1 to do this. Now, this is a 5 by 5 or a five city Travelling Salesman Problem.

We use this data, so we call this city 1 2 3 4 and 5. This is city 1 2 3 4 and 5, now

let us see what we can understand from this matrix. One thing is if the person is at city

1, then the person has to leave city 1 by going to one of these four. Therefore, the

person has to travel a minimum distance of 7 to leave city 1. Similarly, when the person

reaches city 2, the person should travel a minimum distance of 5, a minimum distance

of 8, a minimum distance of 5 and a minimum distance of 6. The sum of these minimum distances

will have to necessarily be some kind of a minimum total distance that this person has

to travel. That is given by the sum of the row minima which is 7 plus 5, 12 plus 8, 20

plus 5, 25 plus 6, 31. This 31 is some kind of a bare minimum that this person has to

travel total distance. This 31 is a lower bound to the actual distance that the person

has to travel. So row minimum gives us a good lower bound and we say that this person has

to travel at least 31. The optimum solution will have to be greater than or equal to the

lower bound of 31. Also, realize that the column subtraction

would also do something. For example, what does this column subtraction tell us? In order

to reach 1, this person should have traveled a minimum of 7, a minimum of 5, a minimum

of 8, a minimum of 5 and a minimum of 6, which would be the same 31 because the travelling

salesman matrix given here is symmetric. Ordinarily, travelling salesman matrices or distance matrices

are given as symmetric because they represent distance. Distance, usually, satisfies symmetry

and triangle inequality. The Travelling Salesman Problem matrix is usually square, symmetric

and satisfies triangle inequality, which means, given any three distances, dij plus djk is

greater than or equal to dik. So, it satisfies this particular inequality also.

Because of this inequality we can always go back and say that if we are looking at a TSP,

the person will visit every city once and only once. If you have a situation where the

person has to come back to that city already visited, then it actually violates the triangle

inequality. Therefore, that will not happen. So, whenever the matrix satisfies triangle

inequality, we can always show that the person will visit every city once and only once.

There can be situations where we do not have a symmetric matrix, in which case, the row

minima could be different from the sum of the column minima. We can consistently use

either the row minima or the column minima to represent the lower bound.

In this case, we are going to use a symmetric matrix. To begin with, if we use the row minima

or the column minima, we are going to get the same 31 as the lower bound. From this,

what else can we do?

We create four branches or n minus 1 branches and say X12 equal to 1, X13 equal to 1, X14

equal to 1 and X15 equal to 1. We do not have X11 equal to 1 because X11 is a subtour of

length 1; you do not have X11 in the solution or Xjj the solution. So, we make four branches

or n minus 1 branches at this stage. When we fix X12 to 1, it means we are assuming

that this person is going to go from 1 to 2. We temporarily leave out this first row

and the second column and then see the additional minimum distance that this person has to travel.

Since we know that he is going from 1 to 2, now having reached 2, the person has to leave

2. Therefore, he would have to travel this row minimum which is 5, this row minimum which

is 8, now this 6 and this 6. So, the sum of the row minima, the moment we fix X12 equal

to 1, we leave out the first row and the second column and for the reduced 4 by 4 matrix we

try to add the row minima. That will become 5 plus 8, 13 plus 6, 19 plus 6, 25, 25 plus

10 we will get 35 as the lower bound. I repeat. We fixed this 10; we leave out the

first row and the second column. For the remaining 4 by 4, the row minimum is 5 plus 8 is 13,

13 plus 6 is 19. This 5 is not counted because this column has been left out. This is 13

plus 6 is 19, 19 plus 6 is 25, 25 plus 10 is 35. The motivation is that the person already

goes from 1 to 2. So in order to go from 2, the person has to travel a minimum of 5. In

order to go from 3, the person has to travel a minimum of 8, here a minimum of 6. This

is not counted because the person has already reached 2. This should not be considered,

so minimum of 6 and yet another minimum of 6, to get a bare minimum of 35, the person

has to travel if you fix this 10. This would tell us that if X12 equal to 1, which means

the person goes from 1 to 2, immediately, the minimum distance that the person travels

should be 35 or more. For 1 3 equal to 1, we can do something similar.

For 1 3, leave this out and leave this column. This goes and take the row minima this 8 is

fixed; the remaining minimum would be 5 plus 8, 13 plus 5, 18 plus 6, 24. I repeat minimum

5, minimum here is 8, minimum here is 5, minimum here is 6, 6plus 5, 11 plus 8, 19 plus 5,

24 plus the fixed 8 would give us 32. If the person goes from 1 to 3, we would say that

the minimum distance the person has to travel is 32. For every i,j that is fixed, leave

out the ith row and jth column; take the reduced matrix and then find out the sum of the row

minima and then add the fixed values to get this 32.

When we fix 1 4, we do this and this goes, so this 9 is fixed; row minimum is 6 here

because this 5 goes; 6 plus 8 is 14, 14 plus 5 is 19, 19 plus 6 is 25, 25 plus 9 is 34.

When we fix 1 5, this row and this column goes; this 7 is fixed, so we have 5, which

is the row minimum; 5 plus 8 is 13, 13 plus 5 is 18, 18 plus 6 is 24, 24 plus 7 is 31.

What we have done is at 1 level, we have said that if the person goes from 1 to 2. It is

35 or more, 32 or more, 34 or more, 31 or more. Then, we want to minimize the total

distance travelled. So, we branch further from this because it has the minimum value

of the lower bound. When we branch from here, you create three more branches. There were

four branches created here, now we have to create three more branches. We now say that

here the person will do X21equal to 1, this will be X23 equal to 1 and this will be X24

equal to 1; we will avoid 2 2 because it is a subtour and we will not have 2 5 because

we already have put 1 5. The person has already reached 5 so the person will not go from 2

to 5 again. From 2 the person can do only these three things. Now, we want to find out

this. To make this better, here, I have 1 5 and 2 1. I have 1 5, so I freeze this row,

this column. I also freeze this row and this column. Effectively, I have only this portion

of the matrix available with me.

What I have here are 3 4 and 5 and I have 2 3 and 4. I have 10 dash 8, 5 8 dash, 6 9

6. We can actually do one more thing. This would mean that 2 to 1 and 1 to 5. I have

2 to 1, 1 to 5, so, I should not have 5 to 2; otherwise it will be a subtour. I put 5

to 2 as another dash here temporarily and then I can find out the row minimum. The row

minimum would give us 8 plus 5, 13 plus 6, 19 and 19 plus the 2 fixed values, that is,

19 plus 7 is 26, 26 plus 10 is 36. Let me repeat this again.

This node I fixed X15 to 1 and X21 to 1. I go back. I leave out the first row fifth column,

second row first column, get the remaining 3 by 3 here. After we get that from the allocation,

I realize that I do 2 to 1 and 1 to 5. So 2 to 1, 1 to 5 would mean, 5 to 2 should not

be there; otherwise, it will become a subtour. I will go back and just put temporarily a

dash here, so that I do not have this and then I compute the row minimum, 8 plus 5 is

13, plus 6 is 19 and 19 plus 10 is 29, plus 7 is 36. Now, to evaluate this 1 5 and 2 3,

I go back, so 3 4 5 and 1 5, this one goes, 2 3 this one goes. So, I have 1 2 and 4 that

is here. The values of 3 to 1 is 8 10 8, 9 5 dash, 7 6 and 6.

I have 1 to 5, now this is 1 to 5 and 2 to 3 and because I have 2 to 3, I should not

have 3 to 2, so I put a dash here and get the row minimum 8 plus 5, 13 plus 6 is 19.

1 to 5 is 19 plus 7 is 26 plus 10, I get 36. So, when I do 1 to 5 and 2 to 3, I get 36

here. I do the third one which is 1 5 2 4. I eliminate this 1 5 and I do 2 4, so I have

3 4 5, 1 2 3, I get 8 10 dash, 9 5 8, 7 6 9. Since, I have 2 4, I should not have 4

2, so the row minimum would give us 8 plus 8 is 16 plus 6 is 22, 22 plus 1 to 5 is 7,

29 plus 2 to 5 is 34, so I get 34 here. Now, I have evaluated up to this. Out of these

nodes which are here, I look at that node which has the minimum value which is 32 here.

I decide to branch from this, so that I may get a solution with 32 or slightly more than

that; branching from here would give me a solution with 36 or more. I would like to

get a smaller value as possible, so I tried to branch this node. I already have 1 3, so

I create three branches here. I put X21 equal to 1, I will not have X22 because it is a

subtour, I will not have X23 because I already have a X13. I will have a X24 equal to 1 and

I will have X25 equal to 1. I will go back and try to find out these three values. For

the first one, I put 1 3 and 2 1. So, 1 3 goes, 2 1 goes, which means, I have these

remaining three. I have 3 4 5 and I have 2 4 5 here. I have used 1 3 and 2 1 and so 2

4 5, 10 8 9, 5 dash 6, 6 6 dash. I have used 1 3 and 2 1. I have 2 to 1, 1 to 3; I should

not have 3 to 2, so 3 to 2 goes from here. Sum of the row minima will be 8 plus 5 is

13, plus 6 is 19, 19 plus 10, 29 plus 8 is 37.

The next one I do 1 3 and 2 4. I eliminated 1 3, I eliminated 2 4 and I have 1 2 and 5

and the values will be 3 1 is 8 10 9, 9 5 6, 7 6 dash. Again, I have used 1 3 and 2

4, because I have 2 4 here and should not have 4 2, otherwise, I will have a subtour;

so, I eliminate this 4 2. I subtract the row minimum 8 plus 6 is 14, plus 6 is 20 and 20

plus 8 is 28, 28 plus 5 is 33. I go back and do 1 3 and 2 5. So 1 3 is here, 2 5 is here

and so 1, 2 and 4 are remaining. So, 3 1 is 8, 3 2 is 10, this is 8, 4 1 is 9, 4 2 is

5, 4 5 is dash, 5 1 is 7, 5 2 is 6, 5 4 is 6. Since I have 2 5 equal to 1, 5 2 will be

not be there, which is a dash. Now, take the row minimum 8 plus 5, 13 plus 6 is 19, 19

plus 6 is 25, 25 8 is 33. Out of these values, I will again try to find out whichever is

the smallest in terms of these values and I branch from there. I could branch from either

this or from this. I look at this; I create two branches, 1 3 2 4, I can do X31. I will

not do it. I can do X31, I cannot do X31 because X13 equal to 1, I cannot do X31.

I do X32, I cannot do X33 because that is a subtour. I will not do X34 because I already

have 2 4 here. I will do X35 equal to 1. I fixed three terms; I have only two more terms

to go. Whenever I have two more terms to go, I do not find the lower bound. I would only

find the upper bound or the feasible solution. I try to find a feasible solution here and

how do I find the feasible solution? I have here 1 to 3, this would mean 1 to 3, 3 to

2, 2 to 4. Automatically, it has to be 4 to 5 and 5 to 1.

So, 1 to 3 is 8, 3 to 2 is 18, 2 to 4 is 23, 4 to 5 is 29, 5 to 1 7 36. So, I have a feasible

solution with Z equal to 36 at this point. The moment I have a feasible solution with

Z equal to 36, I can do a few things. I realize that I do not need to do proceed from here,

because if I proceed from here down, I will get values 37 or more. One of the properties

that we have here in this branch and bound tree is that, as we move down, the value can

only increase and it cannot decrease. When I move down from here, I will get 37 or more.

I already have a solution with 36, so I fathom this because lower bound is greater than current

upper bound. Because this 36 tells me that since I have a feasible solution with 36,

my optimal solution is either 36 or less. Since the lower bound is greater than the

upper bound, there is no point in doing this. Similarly, I can fathom this as well as this,

because even if I proceed from here, I will get 36 or more. I already have a solution

with 36. I am not interested in proceeding from this.

I go back to this one and see what feasible solution I will get now. This is 1 to 3, 3

to 5 and I have 2 to 4. So, this would give me 1 to 3, 2 to 4 and 3 to 5. I will go back.

Therefore 1 to 3, 2 to 4 and 3 to 5 would give me 4 5 and 1 2. 1 to 3, 1 to 3, 2 to

4, 3 to 5 would give me 4 5 and 1 2. I will have 9, 5, 7 6 and since I have 1 to 3, 2

to 4, 3 to 5, so 2 to 4, I will not have 4 to 2 should not be there. So, this is the

only possibility, 4 to 1 and 5 to 2. 5 to 2, 2 to 4 and 4 to 1 is the only possibility

that I can have here. I repeat again. Since, I have 1 to 3, 3 to

5 and I also have 2 to 4, I cannot have 4 to 2. I will only have to move from 5 to 2,

otherwise, I will end up coming back. Therefore, I cannot have 4 to 2. This would give me a

feasible solution 1 to 3, 3 to 5, 5 to 2, 2 to 4, 4 to 1. This gives me a value, 3 to

5 is 8 plus 9 is 17, 17 plus 6 is 23, 23 plus 5 is 28, 28 plus 9 is 37. This gives me Z

equal to 37, which is not being helping me in any way, because this is more than 36 and

therefore, I will not be able to get any gain out of this.

I go back and see whichever is the smallest. This is the smallest, so again I branch from

here. I have done 1 to 3, 2 to 5, so I cannot do 3 to 1, because I have done 1 to 3. I can

do 3 to 2 equal to 1, I will not do 3 to 3, I will do 3 to 4 equal to 1. Each of these

will give me a feasible solution. Here, I get 1 to 3, 3 to 2, 1 to 3, 3 to 2, 2 to 5,

5 to 4 and 4 to 1.

Now, 1 to 3 is 8, 3 to 2 is 18, 2 to 5 is 24, 5 to 4 is 30, 4 to 1 is 39 so Z is equal

to 39. Z equal to 39 is also not going to help me

in anyway so I will start looking at this one. This would give me 1 to 3, 3 to 4. I

have done 1 to 3, 3 to 4. I cannot do 4 to 5; I can do 4 to 2, 2 to 5 and 5 to 1. So,

1 to 3 is 8, 3 to 4 is 8, plus 8 is16, 4 to 2 is 16, plus 5 is 21, 21 plus 6 is 27 plus

7, so, Z equal to 34. The moment I have a solution with Z equal to 34, I realize I can

do many things. This gives me a solution with Z equal to 34. I can fathom this because moving

from here down is only going to give me 35 or more. I can fathom this also because this

moving down is going to give me 34 or more. I can fathom this as well, based on the lower

bound, where proceeding from here is going to give me only 34 or more. At this point,

we realize that we have a feasible solution with 34, which is the best solution and right

now we do not have any other node that is left for evaluation.

All the nodes are now fathomed and these nodes have been fathomed either by feasibility,

feasible solution here, here, here and here, or fathomed based on the condition that lower

bound is greater than upper bound. When there are no more nodes to move around, the algorithm

terminates and in this case it gives us the optimal solution. The best among the feasible

solutions is optimal, so this is the optimal solution: 13 4 2 5 1, where 1 to 3 is 8, 3

to 4 is 16, 4 to 2 plus 5 is 21, 2 to 5 is 21 plus 6 is 27 and plus 7 and Z equal to

34. So, the algorithm terminates with this solution, with this optimal.

Because the problem is symmetric, we would also have got the solution if we had branched

this way, 1 5 2 4 3 1; it would have given us the same value of 34. This is a rudimentary

branch and bound algorithm that we have seen for the Travelling Salesman Problem. This

is a branch and bound algorithm. We have already seen some aspects of branch and bound algorithm

earlier when we did integer programming. In integer programming we said we could fathom

in three ways feasibility, infeasibility and based on the bounds. In this case, we will

not have infeasibility. So we will fathom either based on feasibility or based on this

condition that a lower bound at any node is greater than the current best upper bound.

This is the first rudimentary branch and bound algorithm and computational experience with

this branch and bound algorithm says that this is not very fast or effective. It evaluates

many more nodes. Ordinarily, the bounding strategy comes from

the summation of the row minimum consistently. It also takes much more nodes than we normally

expect. The branching strategy is based on the node that has the smallest value of the

lower bound; the calculation of the bound comes from the minimum. Are there branch and

bound methods which are better than this branch and bound? Now, we will see a couple of more

branch and bound algorithms to the Travelling Salesman Problem in the next lecture.

The Description of Lec-24 Traveling Salesman Problem(TSP)