Clique tree inequalities define facets of the asymmetric traveling salesman polytope

DOI10.1016/0166-218X(93)E0082-AzbMath0819.90121OpenAlexW4251597820MaRDI QIDQ1343150

Matteo Fischetti

Publication date: 1 February 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0082-a

zbMATH Keywords

asymmetric traveling salesman polytopeGrötschel-Pulleyblank clique tree inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items

An extended approach for lifting clique tree inequalities ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ On cardinality constrained cycle and path polytopes ⋮ Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs ⋮ Facets of the \(p\)-cycle polytope ⋮ A polyhedral study of the asymmetric traveling salesman problem with time windows ⋮ A Polyhedral Study of the Quadratic Traveling Salesman Problem

Cites Work

• Unnamed Item
• Unnamed Item
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Facets of the Asymmetric Traveling Salesman Polytope
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph