Recognition of Gilmore-Gomory traveling salesman problem

The best known special case of the traveling salesman problem that is well solved is that due to Gilmore and Gomory. It is a problem of scheduling a heat treatment furnace. In this paper we give a polynomial algorithm for detecting whether or not a given traveling salesman problem is an instance of their problem; we also compute the parameters necessary to apply their algorithm. Thus all such problems can not only be solved in polynomial time but also recognized in polynomial time.