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

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

0.00 Avg rating0 Votes
Article ID: iaor200953687
Country: United States
Volume: 19
Issue: 3
Start Page Number: 356
End Page Number: 365
Publication Date: Jul 2007
Journal: INFORMS Journal On Computing
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.