A BRANCH-AND-CUT ALGORITHM FOR THE SYMMETRICAL GENERALIZED TRAVELING SALESMAN PROBLEM

We consider a variant of the classical symmetric Traveling Salesman Pr oblem in which the nodes are partitioned into clusters and the salesma n has to visit at least one node for each cluster. This NP-hard proble m is known in the literature as the symmetric Generalized Traveling Sa lesman Problem (GTSP), and finds practical applications in routing, sc heduling and location-routing. In a companion paper (Fischetti et al. 1995) we modeled GTSP as an integer linear program, and studied the fa cial structure of two polytopes associated with the problem. Here we p ropose exact and heuristic separation procedures for some classes of f acet-defining inequalities, which are used within a branch-and-cut alg orithm for the exact solution of GTSP. Heuristic procedures are also d escribed. Extensive computational results for instances taken from the literature and involving up to 442 nodes are reported.