Some necessary conditions and a general sufficiency condition for the validity of a Gilmore–Gomory type patching scheme for the traveling salesman problem

One of the most celebrated polynomially solvable cases of the TSP is the Gilmore–Gomory TSP. The patching scheme for the problem developed by Gilmore and Gomory has several interesting features. Its generalization, called the GG-scheme, has been studied by several researchers and polynomially testable sufficiency conditions for its validity have been given, leading to polynomial schemes for large subclasses of the TSP. A good characterization of the subclass of the TSP for which the GG-scheme produces an optimal solution is an outstanding open problem of both theoretical and practical significance. We give some necessary conditions and a new, polynomially testable sufficiency condition for the validity of the GG-scheme that properly includes all previously known such conditions.