Facets of the Asymmetric Traveling Salesman Polytope

DOI10.1287/moor.16.1.42zbMath0742.90079OpenAlexW1978038344MaRDI QIDQ3971736

Matteo Fischetti

Publication date: 25 June 1992

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.16.1.42

zbMATH Keywords

valid inequalitiesfacial structurefacet-defining inequalityasymmetric traveling salesman polytopeSteiner arborescence polytope

Mathematics Subject Classification ID

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

Related Items

A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets ⋮ Clique tree inequalities define facets of the asymmetric traveling salesman polytope ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Complete linear descriptions of small asymmetric traveling salesman polytopes ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. ⋮ A lexicographic semiorder polytope and probabilistic representations of choice ⋮ Unnamed Item ⋮ Facets of two Steiner arborescence polyhedra ⋮ Induced binary probabilities and the linear ordering polytope: A status report ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ On symmetric subtour problems ⋮ Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs ⋮ The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints ⋮ A polyhedral study of the asymmetric traveling salesman problem with time windows ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ Efficient cuts in Lagrangean `relax-and-cut' schemes ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ Survey of facial results for the traveling salesman polytope ⋮ Signed orders, choice probabilities, and linear polytopes