Facets of the Asymmetric Traveling Salesman polytope

Facets of the Asymmetric Traveling Salesman polytope

0.00 Avg rating0 Votes
Article ID: iaor19911710
Country: United States
Volume: 16
Issue: 1
Start Page Number: 42
End Page Number: 56
Publication Date: Feb 1991
Journal: Mathematics of Operations Research
Authors:
Keywords: Traveling salesman problem
Abstract:

This paper considers the Asymmetric Traveling Salesman polytope, equ1, defined as the convex hull of the incidence vectors of tours in a complete digraph with n vertices, and its monotonization, equ2. Several classes of valid inequalities for both these polytopes have been introduced in the literature which are not known to define facets of equ3or equ4. The paper describes a general technique which can often be used to prove that a given inequality defines a facet of equ5. The method is applied to prove that the so-called equ6C3, comb and C2 inequalities define facets ofequ7, thus solving open problems. As for the monotone polytope, a necessary and sufficient condition for a facet-defining inequality of equ8to define a facet of equ9as well, as introduced which applies to the equ10C3, comb and C2 inequalities. In addition, a simple procedure for transforming any facet-defining inequality of equ11into an equivalent one which also defines a facet of equ12, is given.

Reviews

Required fields are marked *. Your email address will not be published.