# Traveling salesman problem

### From Glossary

Given points and a cost matrix, a *tour* is a permutation of the 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, is the sum of its costs:

where is a permutation of The TSP is to find a tour of minimum total cost. The two common integer programming formulations are:

- ILP:

*Subtour elimination constraints:*

- where

- QAP:

- where

In each formulation, 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 which requires The second subtour is eliminated by which requires

In ILP, it is easy to incorporate missing arcs: replace the subscripts with an arc index, Then, the subtour elimination constraints have sums over arcs whose head is in 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.