Jump to content

User:Lesser Cartographies/sandbox/TSP notes

From Wikipedia, the free encyclopedia


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

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

and

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

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

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

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 .