Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem

Abstract

We investigate the family of facet defining inequalities for the asymmetric traveling salesman (ATS) polytope obtainable by lifting the cycle inequalities. We establish several properties of this family that earmark it as the most important among the asymmetric inequalities for the ATS polytope known to date: (1) The family is shown to contain members of unbounded Chvatal rank, whereas most known asymmetric inequalities are of Chvatal rank 1. (2) For large classes within the family a coefficient pattern is identified that makes it easy to develop efficient separation routines. (3) Each member of the family is shown to have a counterpart for the symmetric TS (STS) polytope that is often new, and is obtainable by mapping the inequality for the ATS polytope into a certain face of the STS polytope and then lifting the resulting inequality into one for the STS polytope itself.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1997
Accession Number
ADA352002

Entities

People

  • Egon Balas
  • Matteo Fischetti

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Autonomy
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • British Columbia
  • Coefficients
  • Computer Programming
  • Crossings
  • Elimination
  • Families (Human)
  • Inequalities
  • Integer Programming
  • Linear Algebra
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Marine Ecological Systems Migration