THE SYMMETRICAL GENERALIZED TRAVELING SALESMAN POLYTOPE

The symmetric Generalized Traveling Salesman Problem (GTSP) is a varia nt 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, c alled 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 pa per, 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.