Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality

We report the solution to optimality of ten large-scale symmetric travelling salesman problems. The travelling salesman problem (TSP) is one of the standard problems of the Operations Research/Management Science literature and is cited in virtually every textbook on this subject. The TSP is a hard combinatorial optimization problem for which to date no technically good algorithm is known. All known algorithmic approaches to the TSP that are amenable to a worst-case analysis have yielded nothing for this problem that is as satisfactory as the existing solution procedures for, as an example, flow problems in networks. Furthermore, recent theoretical work has shown that the TSP is algorithmically equivalent to the general zero-one decision problem with linear constraints and objective function. The phrase "This problem is as hard as a travelling salesman problem" reflects this fact and expresses the slim chances of finding an optimal solution to the problem at hand. It is therefore all the more surprising that in the current study, all of the test problems were solved to optimality---i.e., the proposed methodology did not fail on any one of the ten large-scale test problems of the computational study. Besides being a prototype of a difficult combinatorial optimization problem, the travelling salesman problem has a variety of applications in its own right, mostly in the areas of production management, vehicle routing, and vehicle scheduling. A number of related problems, such as, for example, the multiple travelling salesman problem with m travelling salesmen located at a central depot and with fixed charges for their deployment, have been shown elsewhere to fit the standard form of the TSP treated in this paper. The smallest problem of this computational study has 48 cities and the largest one has 318 cities, i.e., the corresponding zero-one linear programming problems have between 1,128 and 50,403 zero-one variables. The algorithmic procedure is a cutting-plane approach coupled with branch-and-bound. For the latter we use the IBM software system MPSX-MIP/370 in a novel (iterative) way. The cutting-planes that we use are subtour-elimination and comb constraints, i.e., they belong to the class of valid inequalities for the symmetric travelling salesman problem which define facets for the associated polytope. This fact, which has been proven mathematically elsewhere, makes the cutting-planes encountered here different from other arbitrary, but valid, cutting-planes encountered in integer programming. In fact, cutting-planes have been virtually abandoned as an algorithmic tool in integer programming because of the erratic behavior of such algorithms exhibited in earlier computational studies. The present study convincingly establishes the usefulness of mathematically proven good cutting-planes as an invaluable algorithmic tool for difficult combinatorial optimization problems. Here the word optimization is taken in its very meaning---we are interested solely in finding a solution that minimizes a cost function and in proving it to be an optimal solution.