Optimizing over the subtour polytope of the travelling salesman problem

DOI10.1007/BF01588786zbMath0726.90086MaRDI QIDQ803048

William R. Pulleyblank, Sylvia Boyd

Publication date: 1990

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

zbMATH Keywords

clique treesChvátal rankpolyhedral aspectssubtour polytopesymmetric travelling salesman

Mathematics Subject Classification ID

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

Related Items (12)

Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming ⋮ Ordered colourings ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ On approximately fair cost allocation in Euclidean TSP games ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Facet Generating Techniques ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ Computing compatible tours for the symmetric traveling salesman problem ⋮ Simpler analysis of LP extreme points for traveling salesman and survivable network design problems ⋮ The indefinite period traveling salesman problem ⋮ TRAVEL - An interactive travelling salesman problem package for the IBM- personal computer ⋮ Survey of facial results for the traveling salesman polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cutting-plane proofs in combinatorial optimization
• The ellipsoid method and its consequences in combinatorial optimization
• Edmonds polytopes and a hierarchy of combinatorial problems
• Facet Generating Techniques
• 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
• Trees and Cuts
• The traveling salesman problem on a graph and some related integer polyhedra
• Multi-Terminal Network Flows
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• On the symmetric travelling salesman problem: A computational study
• On Linear Characterizations of Combinatorial Optimization Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Edmonds polytopes and weakly hamiltonian graphs

This page was built for publication: Optimizing over the subtour polytope of the travelling salesman problem