The Crown Inequalities for the Symmetric Traveling Salesman Polytope

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 ≥ 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.