Optimizing over the subtour polytope of the travelling salesman problem
DOI10.1007/BF01588786zbMATH Open0726.90086MaRDI QIDQ803048FDOQ803048
Authors: Sylvia Boyd, William R. Pulleyblank 
Publication date: 1990
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
clique trees[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Chv%EF%BF%BD%EF%BF%BDtal+rank&go=Go Chv��tal rank]polyhedral aspectssubtour polytopesymmetric travelling salesman
Linear programming (90C05) Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- The traveling salesman problem on a graph and some related integer polyhedra
- The ellipsoid method and its consequences in combinatorial optimization
- 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
- Title not available (Why is that?)
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Multi-Terminal Network Flows
- Title not available (Why is that?)
- Edmonds polytopes and a hierarchy of combinatorial problems
- Edmonds polytopes and weakly hamiltonian graphs
- On cutting-plane proofs in combinatorial optimization
- On the symmetric travelling salesman problem: A computational study
- Facet generating techniques
- Title not available (Why is that?)
- On the symmetric travelling salesman problem: Solution of a 120-city problem
- Title not available (Why is that?)
- On Linear Characterizations of Combinatorial Optimization Problems
- Title not available (Why is that?)
Cited In (13)
- Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
- Computing compatible tours for the symmetric traveling salesman problem
- Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
- On approximately fair cost allocation in Euclidean TSP games
- The indefinite period traveling salesman problem
- Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming
- Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
- Facet generating techniques
- Ordered colourings
- Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
- On symmetric subtour problems
- Survey of facial results for the traveling salesman polytope
- TRAVEL - An interactive travelling salesman problem package for the IBM- personal computer
This page was built for publication: Optimizing over the subtour polytope of the travelling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q803048)
