Research Article Open Access

New Integer Programming Formulations of the Generalized Travelling Salesman Problem

Petrica C. Pop1
  • 1 ,
American Journal of Applied Sciences
Volume 4 No. 11, 2007, 932-937

DOI: https://doi.org/10.3844/ajassp.2007.932.937

Submitted On: 10 June 2007 Published On: 30 November 2007

How to Cite: Pop, P. C. (2007). New Integer Programming Formulations of the Generalized Travelling Salesman Problem . American Journal of Applied Sciences, 4(11), 932-937. https://doi.org/10.3844/ajassp.2007.932.937

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.

  • 1,213 Views
  • 1,589 Downloads
  • 10 Citations

Download

Keywords

  • Traveling salesman problem
  • generalized travelling salesman problem
  • integer programming
  • linear relaxation