zbMATH — the first resource for mathematics

Clique tree inequalities and the symmetric travelling salesman problem. (English) Zbl 0626.90060
The linear programming cutting plane approach for solving the travelling salesman (TS) problem has recently proven to be highly successful and one of the reasons for this success is the fact that instead of ordinary cutting planes, problem-specific cutting planes could be used which define facets of the underlying integer programming polytopes. In this paper, a new class of inequalities (clique tree inequalities) valid for the TS polytope which properly contains many of the known classes of inequalities are defined, and it is shown that all these new inequalities induce facets of the TS polytope. Although no computational results are presented, the authors hope that it will be possible to use the inequalities efficiently in cutting plane procedures for solving the TS problem.
Reviewer: M.M.Syslo

90C10 Integer programming
90C35 Programming involving graphs or networks
52Bxx Polytopes and polyhedra
65K05 Numerical mathematical programming methods
Full Text: DOI