Ladders for Travelling Salesmen
- 1 May 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 5 (2) , 408-420
- https://doi.org/10.1137/0805020
Abstract
We introduce a new class of valid inequalities for the symmetric travelling salesmanpolytope. The family is not of the common handle-tooth variety. We showthat these inequalities are all facet-inducing and have Chv'atal rank 2.Key words: polyhedra, facets, travelling salesman problemAMS 1980 subject classification. Primary: 90C08Copyright (C) by the Society for Industrial and Applied Mathematics, in SIAM Journal on Optimization,5 (1995), pp. 408--420. Research partially supported by...Keywords
This publication has 8 references indexed in Scilit:
- Edmonds polytopes and a hierarchy of combinatorial problemsPublished by Elsevier ,2002
- Hamiltonian path and symmetric travelling salesman polytopesMathematical Programming, 1993
- The Binested Inequalities for the Symmetric Traveling Salesman PolytopeMathematics of Operations Research, 1992
- Small Travelling Salesman PolytopesMathematics of Operations Research, 1991
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman ProblemsSIAM Review, 1991
- Optimizing over the subtour polytope of the travelling salesman problemMathematical Programming, 1990
- Clique Tree Inequalities and the Symmetric Travelling Salesman ProblemMathematics of Operations Research, 1986
- On the symmetric travelling salesman problem II: Lifting theorems and facetsMathematical Programming, 1979