The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities

Sunil Chopra*, Giovanni Rinaldi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

A present trend in the study of the symmetric traveling salesman polytope is to use, as a relaxation of the polytope, the graphical traveling salesman polyhedron (GTSP). Following a parallel approach for the asymmetric traveling salesman polytope, we define the graphical asymmetric traveling salesman problem on a general digraph D and its associated polyhedron GATSP(D). We give basic polyhedral results and lifting theorems for GATSP(D) and we give a general condition for a facet-defining inequality for GTSP to yield a symmetric facet-defining inequality for GATSP. Using this approach we show that all known major families of facet-defining inequalities of GTSP define facets of GATSP. Finally, we discuss possible extension of these results to the asymmetric traveling salesman polytope.

Original languageEnglish (US)
Pages (from-to)602-624
Number of pages23
JournalSIAM Journal on Discrete Mathematics
Volume9
Issue number4
DOIs
StatePublished - Nov 1996
Externally publishedYes

Keywords

  • Directed graph
  • Facet
  • Linear inequality
  • Polyhedron
  • Traveling salesman problem

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities'. Together they form a unique fingerprint.

Cite this