Publications of Giovanni Rinaldi

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Rinaldi G., in the category IASI Research Reports (or show them all):


IASI Research Report n. 249  (Previous    Next)


Naddef D., Giovanni Rinaldi

The crown inequalities for the symmetric traveling Salesman polytope.

ABSTRACT
We define a new family of valid inequalities for the Symmetric Traveling Salesman Polytope (S T S P(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 S T S P(n), for n>8. We describe some extensions of the crown inequalities and we prove that they induce facets of S T S P (n), as well. Finally, we discuss some issues on the possible applications of these inequalities in a polyhedral cutting-plane algorithm.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -