Optimizing over the subtour polytope of the travelling salesman problem

DOI10.1007/BF01588786MaRDI QIDQ803048zbMATH OpenFDO

Authors Sylvia Boyd, William R. Pulleyblank

Publication date 1990

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3943560
• scientific article; zbMATH DE number 3943559
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• A New Formulation for the Travelling Salesman Problem
• Facet identification for the symmetric traveling salesman polytope

Cites work

• scientific article; zbMATH DE number 3646634 (Why is no real title available?)
• scientific article; zbMATH DE number 3943559 (Why is no real title available?)
• scientific article; zbMATH DE number 3943560 (Why is no real title available?)
• scientific article; zbMATH DE number 3499169 (Why is no real title available?)
• scientific article; zbMATH DE number 3353075 (Why is no real title available?)
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• Edmonds polytopes and a hierarchy of combinatorial problems
• Edmonds polytopes and weakly hamiltonian graphs
• Facet generating techniques
• Multi-Terminal Network Flows
• On Linear Characterizations of Combinatorial Optimization Problems
• On cutting-plane proofs in combinatorial optimization
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• On the symmetric travelling salesman problem: A computational study
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The ellipsoid method and its consequences in combinatorial optimization
• The traveling salesman problem on a graph and some related integer polyhedra
• Trees and Cuts

Cited in

(13)

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

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)