Homework Assignment #25

To set up an instance of the TSP for solution by calculating upper and lower bounds for the optimal solution.

Show all work neatly.

For questions 1 and 2, consider the following instance of the TSP with cost matrix $M$:

$$ \left( \begin{array}{ccccc} \infty & 4 & 9 & 2 & 5 \\ 2 & \infty & 7 & 5 & 1 \\ 8 & 3 & \infty & 6 & 4 \\ 1 & 4 & 9 & \infty & 3 \\ 9 & 2 & 7 & 6 & \infty \end{array} \right) $$

in which (for example) it costs 4 to get from city 1 to city 2, there is no edge from city 1 to city 1 (hence the $\infty$), and in general it costs $M[i,j]$ to get from city $i$ to city $j$.

Reduce all rows and columns of the cost matrix $M$. Give both the reduced cost matrix and the resulting lower bound on the cost of the optimal tour.

Generate a quick, correct, but not necessarily optimal solution to this TSP instance (i.e., an initial “BSSF”). List the cities in the resulting tour and give the cost of that tour. This tour cost will be an upper bound on the optimal tour cost.