| y (2007) | |||||||||||||
Abstract | |||||||||||||
| The symmetric Generalized Travelling Salesman Problem (GTSP) is a variant of the classical symmetric Travelling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A dierent 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 nd practical applications in routing and scheduling. 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 (Fischetti, Salazar and Toth [5]), 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. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||