Page locked

This page is currently locked for editing by another user. You have to wait until this user finishes editing or the lock expires.
Currently locked by: 3.144.248.24
Lock expires at: 2024/04/19 13:05 (4 min)
This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Travelling salesman problem ======

<note>This is a playground page for new users. Feel free to edit here!</note>

The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

===== Integer linear programming formulation =====

TSP can be formulated as an integer linear program. Label the cities with the numbers $0, ..., n$ and define:
$$
 x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases}
$$
For $i = 1, ..., n$, let $u_i$ be an artificial variable, and finally take $c_{ij}$ to be the distance from city $i$ to city $j$. Then TSP can be written as the following integer linear programming problem:

\begin{align}
\min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} &&  \\
     & 0 \le x_{ij} \le 1  && i,j=0, \cdots, n  \\
     & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\
     & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\
     & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\
&u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n
\end{align}

The first set of equalities requires that each city be arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one other city. The last constraints enforce that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities. To prove this, it is shown below (1) that every feasible solution contains only one closed sequence of cities, and (2) that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

To prove that every feasible solution contains only one closed sequence of cities, it suffices to show that every subtour in a feasible solution passes through city 0 (noting that the equalities ensure there can only be one such tour). For if we sum all the inequalities corresponding to $x_{ij}=1$ for any subtour of $k$ steps not passing through city 0, we obtain:
$$
nk \leq (n-1)k,
$$
which is a contradiction.

It now must be shown that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.
Without loss of generality, define the tour as originating (and ending) at city 0. Choose $u_{i}=t$ if city $i$ is visited in step $t$ $(i, t = 1, 2, ..., n)$. Then
$$
u_i-u_j\le n-1,
$$
since $u_i$ can be no greater than $n$ and $u_j$ can be no less than 1; hence the constraints are satisfied whenever $x_{ij}=0$. For $x_{ij}=1$, we have
$$u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1,$$
satisfying the constraint.

===== Computing a solution =====

==== Computational complexity ====
The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. 

=== Complexity of approximation ===

In the general case, finding a shortest travelling salesman tour is NPO-complete. If the distance measure is a metric and symmetric, the problem becomes [[https://www.everipedia.com/APX-complete/|APX-complete]] and Christofides’s algorithm approximates it within 1.5.

If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio $0.814 log(n)$; it is an open question if a constant factor approximation exists.
Lehigh ISE / COR@L Lab Wiki

User Tools

Site Tools

Page locked

Page Tools
