Homework Assignment #26

Show all work neatly.

The setting is B&B for TSP. Consider the following reduced cost matrix $M$ for a state, in which $M[i,j] = \infty$ means that the path from $i$ to $j$ has been excluded from consideration (by setting its cost to infinity), with the lower bound lb=25. Note that the edge (2,5) has already been included for the partial tour represented by this state.

$$ M = \left( \begin{array}{cccccc} \infty & 4 & 6 & 0 & \infty & 2 \\ \infty & \infty & \infty & \infty & \infty & \infty \\ 3 & 0 & \infty & 4 & \infty & 7 \\ 5 & 2 & 6 & \infty & \infty & 0 \\ 4 & \infty & 0 & 8 & \infty & 2 \\ 0 & 3 & 1 & 2 & \infty & \infty \end{array} \right) $$

Suppose your algorithm includes the edge from city 5 to city 3 next (this edge has cost 0 relative to the current lower bound lb=25). Give a new reduced cost matrix and new lower bound that have the following properties:

• All edges that can now be excluded from consideration, even on feasibility grounds, have had their entry in the matrix replaced with $\infty$.
• The resulting matrix has been reduced.
• The new lower bound includes the impact of the reduction.

Be sure to think about whether there are other edges you can eliminate; think about ruling out infeasible choices.

Take a look at the new reduced cost matrix. Which edge would you decide to include in a solution next? Justify your answer. (Note that there are several different ways to pick this edge, and each of those selection methods has a good justification.)