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
cities to minimize the total distance covered in a complete circuit? We shall give three formulations of this well-known problem. Let
according to whether the
directed arc on the route is from node
to node
or not. Letting
, the conditions
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37b834abf4b0519efd97e546e339a8662762bef8)
express (a) that if one arrives at city
on step
, one leaves city
on step
, (b) that there is only one direted arc leaving node
, 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
was formulated with only two indicies. Here
according to whether the route from
to
or from
to
was traversed at some time on a route or not. In this case
![{\displaystyle {\begin{aligned}\sum _{i}x_{ij}&=2&(j=1,2,\ldots ,n)\ \\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1eb7701f410e4317bb15da693a06e8c107591a9)
and
![{\displaystyle {\begin{aligned}\sum _{i,j}d_{ij}x_{ij}&=z\ ({\rm {{Min})}}&\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5ebffefe0d36147f26faf063346f1802d6b45a8)
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
are restricted to be integers in the interval
![{\displaystyle {\begin{aligned}0\leq x_{ij}\leq 1\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d194d26de6676f769f59ca646a25009415237504)
since sub-tours like those in Fig. 26-3-IV [omitted] also satisfy the conditions. However, if so-called loop conditions like
![{\displaystyle {\begin{aligned}x_{12}+x_{23}+x_{31}\leq 2\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2f4878f5067268282acf90e061ce0b338cb3883)
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
, depending on whether the salesman travels from city
to
or not, where
. Then an optimal solution can be found by finding integers
, arbitrary real numbers
and
satisfying
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bf1d2b513f0ed68811be2527d58645ccfbe79ad)
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
arcs. In fact, if we add all inequalities corresponding to
around such a loop not passing through city
, we will cancel the differences
and obtain
, a contradiction. We have only to show for any tour starting from
that we can find
that satisfies the third group of conditions. Choose
if city
is visited on the
step where
. It is clear that the difference
for all
. Hence the conditions are satisfied for all
; for
we obtain
.