with respect to their facet-defining properties for the associated polytope. A new class of
inequalities called comb inequalities is derived and their number shown to grow much faster
with the number of cities than the exponentially growing number of subtour-elimination
constraints. The dimension of the travelling salesman polytope is calculated and several
inequalities are shown to define facets of the polytope. In part II (“On the travelling salesman …