# Homework Assignment #26

## Exercises

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

### Question 1

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.

### Question 2

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

Back to top