The problem of separating a class of inequalities that are valid for the symmetric traveling salesman problem (STSP) consists of devising an efficient method that, given a fractional point x* for a relaxation of the STSP, either finds an inequality in the given class of STSP inequalities that is violated by x* or determines that there are no such violated inequalities. We can define important classes of STSP inequalities by performing Naddef's and Rinaldi's node-lifting operation on STSP inequalities defined on small graphs. We present efficient methods for exactly separating large classes of STSP inequalities that arise from an STSP relaxation related to node lifting. In particular, we show how to find efficiently the most-violated inequality in the class of STSP inequalities having a backbone set with a constant number k of vertices, and thus separate in polynomial time the class of all STSP inequalities whose backbone set has at most k vertices.
