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. 204  (Previous    Next)


Padberg M., Giovanni Rinaldi

Facet identification for the symmetric traveling salesman polytope.

ABSTRACT
Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does not belong to the polytope, and returns as output some of the facet inducing inequalities violated by the point. A procedure which always accomplishes this task is called exact, otherwise it is called heuristic. We give exact procedures for the subtour elimination and the 2-matching constraints, based on the Gomory-Hu and Padberg-Rao algorithms respectively. Efficient reduction procedures for the input graph are proposed which accelerate these two algorithms substantially. Exact and heuristic shrinking conditions for the input graph are also given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities. These procedures constitute the core of a polytopal cutting plane algorithm that we have devised and programmed to solve a substantial number of large-scale problem instances with sizes up to 2,392 nodes to optimality.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -