Handles and Teeth in the Symmetric Traveling Salesman Polytope

摘要

In this paper we reivew all the known valid inequalities for the Symmetric Traveling Salesman Polytope that are defined on two underlying families of subsets of the nodes, called handles and teeth. These are, in order of presentation (which is more or less also the chronological one): the subtour elimination inequalities; the comb inequalities; the clique-tree inequalities; the path, wheelbarrow, and bicycle inequalities; the star and hyperstar inequalities; the bipartition inequalities; the star and hyperstar inequalities; the bipartition inequalities; and, finally, the binested inequalities. When known, facet-inducing results are given; in some other cases conjectures are given for such results.