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

Cook W.; Espinoza, DG; Goycoolea M.

Abstract

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. © 2007 INFORMS.

Más información

Título según WOS: Computing with domino-parity inequalities for the traveling salesman problem (TSP)
Título según SCOPUS: Computing with domino-parity inequalities for the traveling salesman problem (TSP)
Título de la Revista: INFORMS JOURNAL ON COMPUTING
Volumen: 19
Número: 3
Editorial: INFORMS
Fecha de publicación: 2007
Página de inicio: 356
Página final: 365
Idioma: English
URL: http://pubsonline.informs.org/doi/abs/10.1287/ijoc.1060.0204
DOI:

10.1287/ijoc.1060.0204

Notas: ISI, SCOPUS