New Integer Programming Formulations of the Generalized Travelling Salesman Problem| Science Publications

American Journal of Applied Sciences

P. C. Pop¹ 

关键词: Traveling salesman problem;    generalized travelling salesman problem;    integer programming;    linear relaxation;   

DOI  :  10.3844/ajassp.2007.932.937

学科分类：自然科学（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown