Survey of facial results for the traveling salesman polytope

DOI10.1016/S0895-7177(98)00041-7zbMath0995.90083OpenAlexW1964218513MaRDI QIDQ1596750

K. S. Ruland, Ervin Y. Rodin

Publication date: 5 May 2002

Published in: Mathematical and Computer Modelling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0895-7177(98)00041-7

zbMATH Keywords

linear programmingfacetsgraphical relaxation polyhedron

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

The pickup and delivery problem: Faces and branch-and-cut algorithm ⋮ Modeling with Metaconstraints and Semantic Typing of Variables ⋮ Galois connections for phylogenetic networks and their polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polyhedral study of the capacitated vehicle routing problem
• Optimizing over the subtour polytope of the travelling salesman problem
• Solution of large-scale symmetric travelling salesman problems
• Classification of travelling salesman problem formulations
• Facet identification for the symmetric traveling salesman polytope
• A cutting plane procedure for the travelling salesman problem on road networks
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• Homotopy and crossings of systems of curves on a surface
• An analytical comparison of different formulations of the travelling salesman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem in graphs with some excluded minors
• A complete description of the traveling salesman polytope on 8 nodes
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Hamiltonian path and symmetric travelling salesman polytopes
• 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
• Graph-theoretic parameters concerning domination, independence, and irredundance
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Branch-and-Cut Approach to a Traveling Salesman Problem with Side Constraints
• The traveling salesman problem on a graph and some related integer polyhedra
• Branch-and-cut approach to a variant of the traveling salesman problem
• On the symmetric travelling salesman problem: A computational study
• Facets of the Asymmetric Traveling Salesman Polytope
• Small Travelling Salesman Polytopes
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• Partial linear characterizations of the asymmetric travelling salesman polytope
• The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities
• Solution of a Large-Scale Traveling-Salesman Problem
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• Maximum matching and a polyhedron with 0,1-vertices