THE SYMMETRICAL GENERALIZED TRAVELING SALESMAN POLYTOPE

The symmetric Generalized Traveling Salesman Problem (GTSP) is a variant of the classical symmetric Traveling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A different version of the problem, called E-GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E-GTSP are NP-hard problems and find practical application's in routing, scheduling, and location-routing. In this paper, we model GTSP and E-GTSP as integer linear programs and study the facial structure of the corresponding polytopes. In a companion paper, the results described in this work have been used to design a branch-and-cut algorithm for the exact solution of instances up to 442 nodes. (C) 1995 John Wiley and Sons, Inc.