A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets

DOI10.1007/BF01581274zbMath0780.90100MaRDI QIDQ2367914

Matteo Fischetti, Egon Balas

Publication date: 17 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

valid inequalitiespolyhedral combinatoricscomplete digraphasymmetric traveling salesman polytopelifting inequalities

Mathematics Subject Classification ID

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

Related Items (20)

Clique tree inequalities define facets of the asymmetric traveling salesman polytope ⋮ The precedence-constrained asymmetric traveling salesman polytope ⋮ A strong flow-based formulation for the shortest path problem in digraphs with negative cycles ⋮ Complete linear descriptions of small asymmetric traveling salesman polytopes ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ Optimizing over the first Chvátal closure ⋮ Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ IFORS' Operational Research Hall of Fame ⋮ A branch-and-cut algorithm for the median-path problem ⋮ New facets of the STS polytope generated from known facets of the ATS polytope ⋮ 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 ⋮ Hamiltonian path and symmetric travelling salesman polytopes ⋮ The asymmetric traveling salesman problem with replenishment arcs ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ Survey of facial results for the traveling salesman polytope

Cites Work

• Unnamed Item
• Facet identification for the symmetric traveling salesman polytope
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• Facets of the Asymmetric Traveling Salesman Polytope
• The Fixed-Outdegree 1-Arborescence Polytope
• Lineare Charakterisierungen von Travelling Salesman Problemen
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph

This page was built for publication: A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets