This homework is concerned with a symmetric traveling salesman problem on eleven vertices (indexed from 0 to 10), with the costs given in the following table:

You will solve this problem using AMPL and CPLEX. Instructions on installing these packages are available from http://www.rpi.edu/~mitchj/ampldetails.html

In your initial formulation use variables x_ij to indicate whether edge (i,j) is used, with x_ij = x_ji and x_ii = 0, and impose the degree constraints that

1. Solve the LP relaxation of the problem, so each x_e satisfies 0 ≤ x_e ≤ 1. Show that this does not give an optimal solution to the TSP. The LP relaxation model and data files are available online.
2. Now require that the solution be integral, in addition to satisfying the degree constraints. Show that this does not give an optimal solution to the TSP.
3. Improve the LP relaxation by adding in the subtour elimination constraints

   for all subsets U ⊆ V of cardinality 3 or 4, where E(U) is the set of edges with both endpoints in U. Show that this does not give an optimal solution to the TSP.

4. Now require that the solution be integral, in addition to satisfying the subtour elimination constraints. Show that this does give an optimal solution to the TSP.
5. Solve the Held and Karp 1-tree relaxation with weights λ_i = 0 for all vertices i, and for one other choice of λ that gives a better lower bound.