Survey of facial results for the traveling salesman polytope

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

Ervin Y. Rodin, K. S. Ruland

Publication date: 5 May 2002

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

zbMATH Keywords

linear programming; facets; graphical relaxation polyhedron

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

The pickup and delivery problem: Faces and branch-and-cut algorithm

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