A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

被引：11

作者：

Jozefowiez, Nicolas ^{[1
,2
]}

Laporte, Gilbert ^{[3
]}

Semet, Frederic ^{[4
]}

机构：

[1] CNRS, LAAS, F-31077 Toulouse, France

[2] Univ Toulouse, UPS, INSA, INP,ISAE,LAAS, F-31077 Toulouse, France

[3] HEC Montreal, CIRRELT, Montreal, PQ H3T 2A7, Canada

[4] Ecole Cent Lille, LAGIS, F-59651 Villeneuve Dascq, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 11期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Minimum labeling problem; Traveling salesman problem; Branch-and-cut;

D O I：

10.1016/j.cor.2011.01.011

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：1534 / 1542

页数：9

共 8 条

[1]

[Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]

[2]

Cerulli R., 2006, ELECT NOTES DISCRETE, V25, P131

[3] The minimum labeling spanning trees [J].

Chang, RS ;

Leu, SJ .

INFORMATION PROCESSING LETTERS, 1997, 63 (05) :277-282

[4] SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM [J].

DANTZIG, G ;

FULKERSON, R ;

JOHNSON, S .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (04) :393-410

[5] EFFICIENT HEURISTICS FOR THE DESIGN OF RING NETWORKS [J].

GENDREAU, M ;

LABBE, M ;

LAPORTE, G .

TELECOMMUNICATION SYSTEMS, 1995, 4 (3-4) :177-188

[6] SYMMETRIC TRAVELING SALESMAN PROBLEM .1. INEQUALITIES [J].

GROTSCHEL, M ;

PADBERG, MW .

MATHEMATICAL PROGRAMMING, 1979, 16 (03) :265-280

[7] AN EFFICIENT ALGORITHM FOR THE MINIMUM CAPACITY CUT PROBLEM [J].

PADBERG, M ;

RINALDI, G .

MATHEMATICAL PROGRAMMING, 1990, 47 (01) :19-36

[8]

Xiong YP, 2007, OPER RES COMPUT SCI, V37, P115

← 1 →