The crown inequalities for the Symmetric Traveling Salesman Polytope

The authors 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. The authors call these inequalities crown inequalities and they prove that they are facet-inducing for STSP (n), for n≥8. The authors describe some extensions of the crown inequalities and they prove that they induce facets of STSP (n), as well. Finally, the authors discuss some issues on the possible applications of these inequalities in a polyhedral cutting-plane algorithm.