ISSN:
1436-4646
Keywords:
Linear Inequalities
;
Convex Polytopes
;
Facets
;
Lifting Theorems
;
Travelling Salesman Problem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem ≥ 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582117
Permalink
