New Integer Programming Formulations of the Generalized Travelling Salesman Problem
Abstract
The Generalized Travelling Salesman Problem, denoted by GTSP, is a variant of the classical travelling salesman problem (TSP), in which the nodes of an undirected graph are partitioned into node sets (clusters) and the salesman has to visit exactly one node from every cluster. In this paper we described six distinct formulations of the GTSP as an integer programming. Apart from the standard formulations all the new formulations that we describe are 'compact' in the sense that the number of constraints and variables is a polynomial function of the number of nodes in the problem. In order to provide compact formulations for the GTSP we used two approaches using auxiliary flow variables beyond the natural binary edge and node variables and the second one by distinguishing between global and local variables. Comparisons of the polytopes corresponding to their linear relaxations are established.
DOI: https://doi.org/10.3844/ajassp.2007.932.937
Copyright: © 2007 Petrica C. Pop. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,360 Views
- 3,221 Downloads
- 97 Citations
Download
Keywords
- Traveling salesman problem
- generalized travelling salesman problem
- integer programming
- linear relaxation