Answer to Question #112029 in Math for Gnanamani CT

Question

Solve the Travelling Salesman Problem using Branch and Bound Technique.

Answer 1

Travelling Salesman Problem using Branch and Bound - Techie Delight

Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

For example, consider below graph. A TSP tour in the graph is A -> B -> C -> D -> B -> A. The cost of the tour is 10 + 25 + 40 + 25 + 10 = 100.

  

In this post, Travelling Salesman Problem using Branch and Bound is discussed.

 

The term Branch and Bound refers to all state space search methods in which all the children of E-node are generated before any other live node can become the E-node. E-node is the node, which is being expended. State space tree can be expended in any method i.e. BFS or DFS. Both start with the root node and generate other nodes. A node which has been generated and all of whose children are not yet been expanded is called live-node. A node is called dead node, which has been generated, but it cannot be expanded further. In this method we expand the node, which is most promising, means the node which promises that expanding or choosing it will give us the optimal solution. So we prepare the tree starting form root then we expand it.

We have a cost Matrix defined by

C(i, j) = W(i, j), if there is a direct path from Ci to Cj

    = INFINTY, if there is no direct path from Ci to Cj

For example, consider below cost matrix M,

 

Here,

C(0, 2) = 30

C(4, 0) = 16

C(1, 1) = INFINITY

Below is state space tree for above TSP problem, which shows optimal solution marked in green

As we can see from above diagram, every node has a cost associated to it. When we we go from city i to city j, cost of a node j will be sum of cost of parent node i, cost of the edge (i, j) and lower bound of the path starting at node j.

As root node is the first node to be expanded, it doesn’t have any parent. So cost will be only lower bound of the path starting at root.

Now how do we calculate lower bound of the path starting at any node?

In general, to get the lower bound of the path starting from the node, we reduce each row and column in such a way that there must be at least one zero in each row and Column. For doing this, we need to reduce the minimum value from each element in each row and column.

Let’s start from root node.

We reduce the minimum value in each row from each element in that row. Minimum in each Row of cost matrix M is marked by blue [10 2 2 3 4] below.

  https://www.techiedelight.com/wp-content/uploads/4.jpg

After reducing the row, we get below reduced matrix.

  https://www.techiedelight.com/wp-content/uploads/5.jpg

We then reduce the minimum value in each column from each element in that column. Minimum in each Column is marked by blue [1 0 3 0 0]. After reducing the column, we get below reduced matrix. This matrix will be further processed by child nodes of root node to calculate their lower bound.

  https://www.techiedelight.com/wp-content/uploads/6.jpg

The total expected cost at the root node is the sum of all reductions.

Cost = [10 2 2 3 4] + [1 0 3 0 0] = 25

Since we have discovered the root node C0, the next node to be expanded can be any node from C1, C2, C3, C4. Whichever node has minimum cost, that node will be expanded further. So we have to find out the expanding cost of each node.

The parent node (C0) has below reduced matrix –

  https://www.techiedelight.com/wp-content/uploads/8.jpg

Lets consider edge from 0 -> 1.

1. As we are adding edge (0, 1) to our search space, we set outgoing edges for city 0 to infinity and all incoming edges to city 1 to infinity. We also set (1, 0) to infinity.

So in reduced matrix of parent node, we change all the elements in row 0 and column 1 and at index (1, 0) to INFINITY (marked in red).

  https://www.techiedelight.com/wp-content/uploads/9.jpg

The resulting cost matrix is:

  https://www.techiedelight.com/wp-content/uploads/10.jpg

2. We try to calculate lower bound of the path starting at node 1 using above resulting cost matrix. The lower bound is 0 as matrix is already in reduced form. i.e. all rows and all columns have zero value.

Therefore for node 1, cost will be

Cost = cost of node 0 +

    cost of the edge(0, 1) +

    lower bound of the path starting at node 1

   = 25 + 10 + 0 = 35

Lets consider edge from 0 -> 2

1. Change all the elements in row 0 and column 2 and at index (2, 0) to INFINITY (marked in red).

  https://www.techiedelight.com/wp-content/uploads/11.jpg

The resulting cost matrix is:

  https://www.techiedelight.com/wp-content/uploads/12.jpg

2. Now calculate lower bound of the path starting at node 2 using the approach discussed earlier. Resultant matrix will be –

  https://www.techiedelight.com/wp-content/uploads/13.jpg

Therefore for node 2, cost will be

Cost = cost of node 0 +

    cost of the edge(0, 2) +

    lower bound of the path starting at node 2

   = 25 + 17 + 11 = 53

Lets consider edge from 0 -> 3.

1. Change all the elements in row 0 and column 3 and at index (3, 0) to INFINITY (marked in red).

  https://www.techiedelight.com/wp-content/uploads/14.jpg

The resulting cost matrix is:

  https://www.techiedelight.com/wp-content/uploads/15.jpg

2. Now calculate lower bound of the path starting at node 3 using the approach discussed earlier. Lower bound of the path starting at node 3 is 0 as it is already in reduced form. i.e. all rows and all columns have zero value.

Therefore for node 3, cost will be

Cost = cost of node 0 +

    cost of the edge(0, 3) +

    lower bound of the path starting at node 3

   = 25 + 0 + 0 = 25

Similarly, we calculate cost for 0 -> 4. Its cost will be 31.

Now we find a live node with least estimated cost. Live nodes 1, 2, 3, and 4 has costs 35, 53, 25 and 31 respectively. The minimum among them is Node 3 having cost 25. So node 3 will be expanded further as shown in state space tree diagram. After adding its children to list of live nodes, we again find a live node with least cost and expand it. We continue the search till a leaf is encountered in space search tree. If a leaf is encountered, then the tour is completed and we will return back to the root node.