Clique tree inequalities and the symmetric travelling salesman problem.

*(English)*Zbl 0626.90060The 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