 # Traveling salesman problem

Given $LaTeX: n$ points and a cost matrix, $LaTeX: [c_{ij}],$ a tour is a permutation of the $LaTeX: n$ points. The points can be cities, and the permutation the visitation of each city exactly once, then returning to the first city (called home). The cost of a tour, $LaTeX: ,$ is the sum of its costs: $LaTeX: c_{i_1 i_2} + c_{i_2 i_3} + \dots + c_{i_{n-1} i_n} + c_{i_n i_1},$

where $LaTeX: (i_1, i_2, \dots, i_n)$ is a permutation of $LaTeX: \{1,\dots,n\}.$ The TSP is to find a tour of minimum total cost. The two common integer programming formulations are:

ILP: $LaTeX: \min \left\{ \sum_{ij} c_{ij} x_{ij} : x \in P, \, x_ij \in \{0, 1\} \right\}$

Subtour elimination constraints: $LaTeX: \sum_{i,j \in V} x_{ij} \le |V| - 1 \mbox{ for } \empty \ne V \subset \{1, \dots , n \} (V \ne \{ 1, \dots, n \} ),$

where $LaTeX: x_{ij} = \begin{cases} 1 & \mbox{ if city } j \mbox{ follows city } i \mbox{ in the tour} \\ 0 & \mbox{ otherwise} \end{cases}$

QAP: $LaTeX: \min \left\{ \sum_{ij} c_{ij} \left( \sum_{k=1}^{n-1} x_{ik} x_{j \, k+1} + x_{i n} x_{j 1} \right) : x \in P, \, x_{i j} \in \{0 , 1\} \right\} ,$

where $LaTeX: x_{(i, j)} = \begin{cases} 1 & \mbox{ if city } j \mbox{ follows city } i \mbox{ in the tour} \\ 0 & \mbox{ otherwise} \end{cases}$

In each formulation, $LaTeX: P$ is the assignment polytope. The subtour elimination constraints in ILP eliminate assignments that create cycles, such as shown in the following figure:

The first subtour is eliminated by $LaTeX: V = \{1, 2, 3\},$ which requires $LaTeX: x_{12} + x_{23} + x_{31} \le 2.$ The second subtour is eliminated by $LaTeX: V = \{4, 5\},$ which requires $LaTeX: x_{45} + x_{54} \le 1.$

In ILP, it is easy to incorporate missing arcs: replace the subscripts $LaTeX: (ij)$ with an arc index, $LaTeX: k.$ Then, the subtour elimination constraints have sums over arcs whose head is in $LaTeX: V.$ The quadratic assignment problem formulation (QAP) is well suited to certain solution methods, such as neural networks.

When the cost matrix is symmetric, it is called the symmetric TSP. When the points are in the plane, and the cost matrix is the Euclidean distance matrix, it is called the Euclidean TSP. See the n-Opt heuristic.