User:Lesser Cartographies/sandbox/TSP notes

Dantzig, George B. (1963), Linear Programming and Extensions, Princeton, NJ: PrincetonUP, pp. 545–7, ISBN 0-691-08000-3, sixth printing, 1974.

[n.b. Equation numbers omitted.]

The Problem. In what order should a traveling salesman visit $n$ cities to minimize the total distance covered in a complete circuit? We shall give three formulations of this well-known problem. Let $x_{ijt}={\rm {1\ or\ 0}}$ according to whether the $t^{\rm {th}}$ directed arc on the route is from node $i$ to node $j$ or not. Letting $x_{ijn+1}\equiv x_{ij1}$, the conditions

${\begin{aligned}\sum _{i}x_{ijt}&=\sum _{k}x_{j,k,t+1}&(j,t=1,\ldots ,n)\\\sum _{j,t}x_{ijt}&=1&(i=1,\ldots ,n)\\\sum _{i,j,t}d_{ij}x_{ijt}&=z\ ({\rm {{Min})}}&\\\end{aligned}}$

express (a) that if one arrives at city $j$ on step $t$, one leaves city $j$ on step $t+1$, (b) that there is only one direted arc leaving node $i$, and (c) the length of the tour is minimum. It is not difficult to see that an integer solution to this system is a tour [Flood, 1956-1].

In two papers by Dantzig, Fulkerson, and Johnson [1954-1, 1959-1], the case of a symmetric distance $d_{ij}=d_{ji}$ was formulated with only two indicies. Here $x_{ji}\equiv x_{ij}=1\ {\rm {{or}\ 0}}$ according to whether the route from $i$ to $j$ or from $j$ to $i$ was traversed at some time on a route or not. In this case

${\begin{aligned}\sum _{i}x_{ij}&=2&(j=1,2,\ldots ,n)\ \\\end{aligned}}$

and

${\begin{aligned}\sum _{i,j}d_{ij}x_{ij}&=z\ ({\rm {{Min})}}&\\\end{aligned}}$

express the condition that the sum of the number of entries and departures for each node is two. Note in this case that no distinction is made between the two possible directions that one could traverse an arc between two cities. These conditions are not enough to characterize a tour even though the $x_{ij}$ are restricted to be integers in the interval

${\begin{aligned}0\leq x_{ij}\leq 1\\\end{aligned}}$

since sub-tours like those in Fig. 26-3-IV [omitted] also satisfy the conditions. However, if so-called loop conditions like

${\begin{aligned}x_{12}+x_{23}+x_{31}\leq 2\end{aligned}}$

are imposed as added constraints as required, these will rule out integer solutions which are not admissible.

[Exercise omitted.]

A third way to reduce a traveling-salesman problem to an integer program is due to A. W. Tucker [1960-1]. It has less constraints and variables than those above. Let $x_{ij}=1\ {\rm {{or}\ 0}}$, depending on whether the salesman travels from city $i$ to $j$ or not, where $i=0,1,2,\ldots ,n$. Then an optimal solution can be found by finding integers $x_{ij}$, arbitrary real numbers $u_{i}$ and ${\rm {{Min}\ z}}$ satisfying

${\begin{aligned}\sum _{i=0}^{n}x_{ij}&=1&(j=1,2,\ldots ,n)\\\sum _{j=0}^{n}x_{ij}&=1&(i=1,2,\ldots ,n)\\u_{i}-u_{j}+nx_{ij}&\leq n-1&(1\leq i\neq j\leq n)\\\sum _{i=0}^{n}\sum _{j=0}^{n}d_{ij}x_{ij}&=z\ ({\rm {{Min})}}&\\\end{aligned}}$

The third group of conditions is violated whenever we have an integer soulution to the first two groups that is not a tour, for in this case it contains two or more loops with $k<n$ arcs. In fact, if we add all inequalities corresponding to $x_{ij}=1$ around such a loop not passing through city $0$, we will cancel the differences $u_{i}-u_{j}$ and obtain $nk\leq (n-1)k$, a contradiction. We have only to show for any tour starting from $i=0$ that we can find $u_{i}$ that satisfies the third group of conditions. Choose $u_{i}=t$ if city $i$ is visited on the $t^{\rm {th}}$ step where $t=1,2,\ldots ,n$. It is clear that the difference $u_{i}-u_{j}\leq n-1$ for all $(i,j)$. Hence the conditions are satisfied for all $x_{ij}=0$; for $x_{ij}=1$ we obtain $u_{i}-u_{j}+nx_{ij}=(t)-(t+1)+n=n-1$.