Facets of the Asymmetric Traveling Salesman Polytope

DOI10.1287/MOOR.16.1.42zbMATH Open0742.90079OpenAlexW1978038344MaRDI QIDQ3971736FDOQ3971736

Authors: 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

Recommendations

• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities
• Facet identification for the symmetric traveling salesman polytope
• An analysis of the asymmetric quadratic traveling salesman polytope
• The facets of the asymmetric 5-city traveling salesman polytope
• Symmetric Inequalities and Their Composition for Asymmetric Travelling Salesman Polytopes
• On the facial structure of symmetric and graphical traveling salesman polyhedra
• A procedure of facet composition for the Symmetric Traveling Salesman Polytope

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)

Cited In (36)

• New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
• Title not available (Why is that?)
• Title not available (Why is that?)
• Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem
• Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups.
• Improved Computational Approaches and Heuristics for Zero Forcing
• Signed orders, choice probabilities, and linear polytopes
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• A polyhedral study of the asymmetric traveling salesman problem with time windows
• Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
• A lexicographic semiorder polytope and probabilistic representations of choice
• Complete linear descriptions of small asymmetric traveling salesman polytopes
• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• SelfSplit parallelization for mixed-integer linear programming
• Facets and rank of integer polyhedra
• A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs
• Asymmetric multidepot vehicle routing problems: valid inequalities and a branch-and-cut algorithm
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• A branch-and-cut framework for the consistent traveling salesman problem
• Facets of two Steiner arborescence polyhedra
• Induced binary probabilities and the linear ordering polytope: A status report
• Facet generating techniques
• Facets of the \((s,t)-p\)-path polytope
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• The Fixed-Outdegree 1-Arborescence Polytope
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• The facets of the asymmetric 5-city traveling salesman polytope
• The precedence-constrained asymmetric traveling salesman polytope
• On symmetric subtour problems
• Combined route capacity and route length models for unit demand vehicle routing problems
• Exact methods for solving the elementary shortest and longest path problems
• Title not available (Why is that?)
• Survey of facial results for the traveling salesman polytope
• On the Asymmetric Connected Facility Location Polytope
• Clique tree inequalities define facets of the asymmetric traveling salesman polytope

This page was built for publication: Facets of the Asymmetric Traveling Salesman Polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3971736)