Using DP-constraints to obtain improved TSP solutions.

Abstract

The Travelling Salesman Problem (TSP) is a well-known NP-hard problem. Although it is unlikely that an efficient algorithm will ever be found for the TSP, some success has been achieved for large real-world instances by using the branch and cut technique. This technique requires knowledge of classes of useful valid inequalities for the polytope associated with the TSP, as well as efficient separation routines for these classes of inequalities. The DP-constraints are a recently discovered class of valid inequalities for the TSP which contain the famous comb inequalities. An efficient separation routine is known for these constraints if certain conditions are satisfied by the point to be separated. This separation routine has never been implemented or tested. We present several performance enhancements that we made to the existing separation routine for these constraints and discuss our implementation of this improved algorithm. Our implementation runs in O(n3 lg n), where n is the number of vertices in the graph. We also show how the outcome of the separation routine can be translated into a DP-constraint that is in a suitable form for testing. We test our implementation and provide results that we believe show the usefulness of these inequalities and the separation routine within a branch and cut framework for the TSP.