Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications. 1. The Cutting-Plane Method The symmetric traveling salesman problem, or TSP for short, is this: given a nite number of \cities" along with the cost of travel between each pair of them, nd the cheapest way of visiting all of the cities and returning to your starting point. The travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X; the \way of visiting all of the cities" is simply the order in which the cities are visited. The prominence of the TSP in the combinatorial optimization literature is to a large extent due to its success as an engine-of-discovery for techniques that have application far beyond the narrow con nes of the TSP itself. Foremost among the TSP-inspired discoveries is Dantzig, Fulkerson, and Johnson's (1954) cutting-plane method, which can be used to attack any problem minimize cx subject to x 2 S (1) such that S is a nite subset of some R and such that an eÆcient algorithm to recognize points of S is available. This method is iterative; each of its D. Applegate: Algorithms and Optimization Department, AT&T Labs { Research, Florham Park, NJ 07932, USA R. Bixby: Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA V. Chv atal: Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA W. Cook: Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA ? Supported by ONR Grant N00014-03-1-0040 2 David Applegate et al. iterations begins with a linear programming (LP) relaxation of (1), meaning a problem minimize cx subject to Ax b (2) such that the polyhedron P de ned as fx : Ax bg contains S and is bounded. Since P is bounded, we can nd an optimal solution x of (2) such that x is an extreme point of P . If x belongs to S, then it constitutes an optimal solution of (1); otherwise some linear inequality is satis ed by all the points in S and violated by x ; such an inequality is called a cutting plane or simply a cut . In the latter case, we nd a nonempty family of cuts, add them to the system Ax b, and use the resulting tighter relaxation of (1) in the next iteration of the procedure. Dantzig et al. demonstrated the power of their cutting-plane method by solving a 49-city instance of the TSP, which was an impressive size in 1954. The TSP is a special case of (1) with m = n(n 1)=2, where n is the number of the cities, and with S consisting of the set of the incidence vectors of all the Hamiltonian cycles through the set V of the n cities; in this context, Hamiltonian cycles are commonly called tours. In Dantzig et al.'s attack, the initial P consists of all vectors x, with components subscripted by edges of the complete graph on V , that satisfy 0 xe 1 for all edges e (3) and P (xe : v 2 e) = 2 for all cities v. (4) (Throughout this paper, we treat the edges of a graph as two-point subsets of its vertex-set: v 2 emeans that vertex v is an endpoint of edge e;  6= ; means that edge e has an endpoint in set Q; e Q 6= ;means that edge e has an endpoint outside setQ; and so on.) All but two of their cuts have the form P (xe : e\Q 6= ;; e Q 6= ;) 2 such that Q is a nonempty proper subset of V . Dantzig et al. called such inequalities \loop constraints"; nowadays, they are commonly referred to as subtour elimination inequalities ; we are going to call them simply subtour inequalities . (As for the two exceptional cuts, Dantzig et al. give ad hoc combinatorial arguments to show that these inequalities are satis ed by incidence vectors of all tours through the 49 cities and, in a footnote, they say \We are indebted to I. Glicksberg of Rand for pointing out relations of this kind to us.") The original TSP algorithm of Dantzig et al. has been extended and improved by many researchers, led by the fundamental contributions of M. Grotschel and M. Padberg; surveys of this work can be found in Grotschel and Padberg (1985), Padberg and Gr otschel (1985), J unger et al.