Computing with domino-parity inequalities for the traveling salesman problem (TSP).

We describe methods for implementing separation algorithms for domino-parity inequalities for the symmetric traveling salesman problem. These inequalities were introduced by Letchford (2000), who showed that the separation problem can be solved in polynomial time when the support graph of the LP solution is planar. In our study we deal with the problem of how to use this algorithm in the general (nonplanar) case, continuing the work of Boyd et al. (2001). Our implementation includes pruning methods to restrict the search for dominoes, a parallelization of the main domino-building step, heuristics to obtain planar-support graphs, a safe-shrinking routine, a random-walk heuristic to extract additional violated constraints, and a tightening procedure to modify existing inequalities as the LP solution changes. We report computational results showing the strength of the new routines, including the optimal solution of a 33,810-city instance from the TSPLIB.

Key words: combinatorial optimization; traveling salesman problem; cutting-plane algorithm

1. Introduction

We consider the traveling salesman problem (TSP) with symmetric travel costs, that is, the cost to travel from city a to city b is the same as traveling from b to a. The input to the problem can be described as a complete graph G = (V, E) with nodes V, edges E, and edge costs ([c.sub.e]: e [member of] E). Here V represents the cities and the problem is to find a tour of minimum total edge cost, where a tour is a cycle that visits each node exactly once (also known as a Hamiltonian cycle).

The TSP has long been an active platform for testing new ideas in integer programming and combinatorial optimization. Among the solution techniques proposed to date, the most successful has been the Dantzig et al. (1954) cutting-plane method. In their work, a tour is represented as a 0/1 vector x = ([x.sub.e]: e [member of] E), where [x.sub.e] = 1 if edge e is used in the tour and [x.sub.e] = 0 otherwise. Given any linear system Ax [less than or equal to] b that is satisfied by every tour vector, the solution of the linear-programming (LP) problem

minimize [summation over (e[member of]E)][c.sub.e][x.sub.e] subject to Ax [less than or equal to] b

provides a lower bound for the TSP. The cutting-plane method improves this bound by iteratively adding further linear inequalities, or cutting planes, that are satisfied by all tour vectors but not satisfied by the current LP solution vector x*; the task of finding such violated inequalities among a specified class is known as the separation problem for the class. Surveys of the wide body of work on the cutting-plane method for the TSP can be found in Junger et al. (1995) and Naddef (2002).