MATP6620/DSES6760 Combinatorial Optimization & Integer Programming
Homework 1.

Due: Thursday, January 22, 2009.

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:

$$\begin{array}{r\vert rrrrrrrrrrr} & 0 & 1 & 2 & 3 & 4 & 5 & ... ...93 & 91 & 92 & 14 & 93 & 92 & 91 & 93 & 62 & 63 & 0 \end{array}$$

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

$$\sum_{j \neq i} x_{ij} \; = \; 2 \qquad \mbox{ for } i = 0, \ldots,10$$

1. Solve the LP relaxation of the problem, so each $x_e$ satisfies $0 \leq x_e \leq 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
   
   $$\sum_{e \in E(U)} x_e \leq \vert U\vert - 1$$
   
   
   for all subsets $U \subseteq 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.

	John Mitchell
	Amos Eaton 325
	x6915.
	mitchj at rpi dot edu
	Office hours: by appointment, since there are no classes on Monday.