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.

After reducing the row, we get below reduced matrix.

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.

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 –

**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).

The resulting cost matrix is:

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).

The resulting cost matrix is:

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

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).

The resulting cost matrix is:

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.

Below is C++ implementation of above idea –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 |
#include <bits/stdc++.h> using namespace std; // N is number of total nodes on the graph or the cities in the map #define N 5 // Sentinel value for representing infinity #define INF INT_MAX // State Space Tree nodes struct Node { // stores edges of state space tree // helps in tracing path when answer is found vector<pair<int, int>> path; // stores the reduced matrix int reducedMatrix[N][N]; // stores the lower bound int cost; //stores current city number int vertex; // stores number of cities visited so far int level; }; // Function to allocate a new node (i, j) corresponds to visiting // city j from city i Node* newNode(int parentMatrix[N][N], vector<pair<int, int>> path, int level, int i, int j) { Node* node = new Node; // stores ancestors edges of state space tree node->path = path; // skip for root node if (level != 0) // add current edge to path node->path.push_back(make_pair(i, j)); // copy data from parent node to current node memcpy(node->reducedMatrix, parentMatrix, sizeof node->reducedMatrix); // Change all entries of row i and column j to infinity // skip for root node for (int k = 0; level != 0 && k < N; k++) { // set outgoing edges for city i to infinity node->reducedMatrix[i][k] = INF; // set incoming edges to city j to infinity node->reducedMatrix[k][j] = INF; } // Set (j, 0) to infinity // here start node is 0 node->reducedMatrix[j][0] = INF; // set number of cities visited so far node->level = level; // assign current city number node->vertex = j; // return node return node; } // Function to reduce each row in such a way that // there must be at least one zero in each row int rowReduction(int reducedMatrix[N][N], int row[N]) { // initialize row array to INF fill_n(row, N, INF); // row[i] contains minimum in row i for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (reducedMatrix[i][j] < row[i]) row[i] = reducedMatrix[i][j]; // reduce the minimum value from each element in each row for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (reducedMatrix[i][j] != INF && row[i] != INF) reducedMatrix[i][j] -= row[i]; } // Function to reduce each column in such a way that // there must be at least one zero in each column int columnReduction(int reducedMatrix[N][N], int col[N]) { // initialize col array to INF fill_n(col, N, INF); // col[j] contains minimum in col j for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (reducedMatrix[i][j] < col[j]) col[j] = reducedMatrix[i][j]; // reduce the minimum value from each element in each column for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (reducedMatrix[i][j] != INF && col[j] != INF) reducedMatrix[i][j] -= col[j]; } // Function to get the lower bound on // on the path starting at current min node int calculateCost(int reducedMatrix[N][N]) { // initialize cost to 0 int cost = 0; // Row Reduction int row[N]; rowReduction(reducedMatrix, row); // Column Reduction int col[N]; columnReduction(reducedMatrix, col); // the total expected cost // is the sum of all reductions for (int i = 0; i < N; i++) cost += (row[i] != INT_MAX) ? row[i] : 0, cost += (col[i] != INT_MAX) ? col[i] : 0; return cost; } // print list of cities visited following least cost void printPath(vector<pair<int, int>> list) { for (int i = 0; i < list.size(); i++) cout << list[i].first + 1 << " -> " << list[i].second + 1 << endl; } // Comparison object to be used to order the heap struct comp { bool operator()(const Node* lhs, const Node* rhs) const { return lhs->cost > rhs->cost; } }; // Function to solve Traveling Salesman Problem using Branch and Bound int solve(int costMatrix[N][N]) { // Create a priority queue to store live nodes of search tree; priority_queue<Node*, std::vector<Node*>, comp> pq; vector<pair<int, int>> v; // create a root node and calculate its cost // The TSP starts from first city i.e. node 0 Node* root = newNode(costMatrix, v, 0, -1, 0); // get the lower bound of the path starting at node 0 root->cost = calculateCost(root->reducedMatrix); // Add root to list of live nodes; pq.push(root); // Finds a live node with least cost, add its children to list of // live nodes and finally deletes it from the list while (!pq.empty()) { // Find a live node with least estimated cost Node* min = pq.top(); // The found node is deleted from the list of live nodes pq.pop(); // i stores current city number int i = min->vertex; // if all cities are visited if (min->level == N - 1) { // return to starting city min->path.push_back(make_pair(i, 0)); // print list of cities visited; printPath(min->path); // return optimal cost return min->cost; } // do for each child of min // (i, j) forms an edge in space tree for (int j = 0; j < N; j++) { if (min->reducedMatrix[i][j] != INF) { // create a child node and calculate its cost Node* child = newNode(min->reducedMatrix, min->path, min->level + 1, i, j); /* Cost of the child = cost of parent node + cost of the edge(i, j) + lower bound of the path starting at node j */ child->cost = min->cost + min->reducedMatrix[i][j] + calculateCost(child->reducedMatrix); // Add child to list of live nodes pq.push(child); } } // free node as we have already stored edges (i, j) in vector. // So no need for parent node while printing solution. free(min); } } // main function int main() { // cost matrix for traveling salesman problem. /* int costMatrix[N][N] = { {INF, 5, INF, 6, 5, 4}, {5, INF, 2, 4, 3, INF}, {INF, 2, INF, 1, INF, INF}, {6, 4, 1, INF, 7, INF}, {5, 3, INF, 7, INF, 3}, {4, INF, INF, INF, 3, INF} }; */ // cost 34 int costMatrix[N][N] = { { INF, 10, 8, 9, 7 }, { 10, INF, 10, 5, 6 }, { 8, 10, INF, 8, 9 }, { 9, 5, 8, INF, 6 }, { 7, 6, 9, 6, INF } }; /* // cost 16 int costMatrix[N][N] = { {INF, 3, 1, 5, 8}, {3, INF, 6, 7, 9}, {1, 6, INF, 4, 2}, {5, 7, 4, INF, 3}, {8, 9, 2, 3, INF} }; */ /* // cost 8 int costMatrix[N][N] = { {INF, 2, 1, INF}, {2, INF, 4, 3}, {1, 4, INF, 2}, {INF, 3, 2, INF} }; */ /* // cost 12 int costMatrix[N][N] = { {INF, 5, 4, 3}, {3, INF, 8, 2}, {5, 3, INF, 9}, {6, 4, 3, INF} }; */ cout << "\n\nTotal Cost is " << solve(costMatrix); return 0; } |

**Output: **

1 -> 3

3 -> 4

4 -> 2

2 -> 5

5 -> 1

Total Cost is 34

*The proposed method, which is using Branch & Bound, is better because it prepares the matrices in different steps. At each step the cost matrix is calculated. From the initial point we come to know that what can be the minimum cost of the tour. The cost in the initial stages is not exact cost but it gives some idea because it is the approximated cost. At each step it gives us the strong reason that which node we should travel the next and which one not. It gives this fact in terms of the cost of expanding a particular node.
*

**References:**

https://www.seas.gwu.edu/~bell/csci212/Branch_and_Bound.pdf

http://research.ijcaonline.org/volume65/number5/pxc3885866.pdf

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂