THE CROWN INEQUALITIES FOR THE SYMMETRICAL TRAVELING SALESMAN POLYTOPE

被引：15

作者：

NADDEF, D

RINALDI, G

机构：

[1] ESA UNIV SCI SOCIALES GRENOBLE,F-38041 GRENOBLE,FRANCE

[2] CNR,IST ANAL SISTEMI & INFORMAT,I-00185 ROME,ITALY

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1992年 / 17卷 / 02期

关键词：

SYMMETRICAL TRAVELING SALESMAN PROBLEM; GRAPHICAL TRAVELING SALESMAN PROBLEM; POLYHEDRON; FACET; LINEAR INEQUALITIES;

D O I：

10.1287/moor.17.2.308

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We define a new family of valid inequalities for the Symmetric Traveling Salesman Polytope (STSP(n)), that is, the convex hull of the incidence vectors of all Hamiltonian cycles of a complete graph with n nodes. The smallest value of n for which the inequalities are defined is 8. We call these inequalities crown inequalities and we prove that they are facet-inducing for STSP(n), for n greater-than-or-equal-to 8. We describe some extensions of the crown inequalities and we prove that they induce facets of STSP(n), as well. Finally, we discuss some issues on the possible applications of these inequalities in a polyhedral cutting-plane algorithm.

引用

页码：308 / 326

页数：19

共 19 条

[1]

BOYD S, 1988, IN PRESS MATH OPER R

[2]

Chvatal V., 1973, Mathematical Programming, V5, P29, DOI 10.1007/BF01580109

[3] THE TRAVELING SALESMAN PROBLEM ON A GRAPH AND SOME RELATED INTEGER POLYHEDRA [J].