SOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMS

被引：122

作者：

GROTSCHEL, M ^{[1
]}

HOLLAND, O ^{[1
]}

机构：

[1] UNIV BONN,INST OPERAT RES,FORSCHUNGSINST DISKRETE MATH,W-5300 BONN,GERMANY

来源：

MATHEMATICAL PROGRAMMING | 1991年 / 51卷 / 02期

关键词：

TRAVELING SALESMAN PROBLEM; CUTTING PLANE ALGORITHMS; POLYHEDRAL COMBINATORICS;

D O I：

10.1007/BF01586932

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.

引用

页码：141 / 202

页数：62

共 28 条

[1]

[Anonymous], 1954, OPERATIONS RES, DOI DOI 10.1287/OPRE.2.4.393

[2]

Bland R. E., 1987, 730 CORN U SCH ORIE

[3] SOLVING LARGE-SCALE SYMMETRIC TRAVELING SALESMAN PROBLEMS TO OPTIMALITY [J].

CROWDER, H ;

PADBERG, MW .

MANAGEMENT SCIENCE, 1980, 26 (05) :495-509

[4] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[5]

FELTS W, 1971, COMMUN ACM, V14, P327

[6]

GLOVER F, CCS, V362

[7] MULTI-TERMINAL NETWORK FLOWS [J].

GOMORY, RE ;

HU, TC .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04) :551-570

[8] SOLVING MATCHING PROBLEMS WITH LINEAR-PROGRAMMING [J].

GROTSCHEL, M ;

HOLLAND, O .

MATHEMATICAL PROGRAMMING, 1985, 33 (03) :243-259

[9] CLIQUE TREE INEQUALITIES AND THE SYMMETRICAL TRAVELING SALESMAN PROBLEM [J].

GROTSCHEL, M ;

PULLEYBLANK, WR .

MATHEMATICS OF OPERATIONS RESEARCH, 1986, 11 (04) :537-569

[10] SYMMETRIC TRAVELING SALESMAN PROBLEM .2. LIFTING THEOREMS AND FACETS [J].

GROTSCHEL, M ;

PADBERG, MW .

MATHEMATICAL PROGRAMMING, 1979, 16 (03) :281-302

← 1 2 3 →