On the symmetric travelling salesman problem I: Inequalities
From MaRDI portal
Publication:3048580
DOI10.1007/BF01582116zbMath0413.90048MaRDI QIDQ3048580
Manfred W. Padberg, Martin Grötschel
Publication date: 1979
Published in: Mathematical Programming (Search for Journal in Brave)
integer programming; combinatorial inequalities; general comb in a graph; hard combinatorial optimization problem; symmetric n-city traveling salesman problem
90C10: Integer programming
52A40: Inequalities and extremum problems involving convexity in convex geometry
52Bxx: Polytopes and polyhedra
Related Items
A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program, Polyhedral techniques in combinatorial optimization I: Theory, Classical cuts for mixed-integer programming and branch-and-cut, Minimum-weight two-connected spanning networks, Polyhedral study of the capacitated vehicle routing problem, A spectral approach to polyhedral dimension, Optimizing over the subtour polytope of the travelling salesman problem, Solution of large-scale symmetric travelling salesman problems, On the graphical relaxation of the symmetric traveling salesman polytope, Chvátal closures for mixed integer programming problems, Recent advances in vehicle routing exact algorithms, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Certification of an optimal TSP tour through 85,900 cities, The optimum assignments and a new heuristic approach for the traveling salesman problem, \(K_ i\)-covers. I: Complexity and polytopes, A cutting plane procedure for the travelling salesman problem on road networks, A new class of cutting planes for the symmetric travelling salesman problem, On cutting-plane proofs in combinatorial optimization, On minimal Eulerian graphs, Polyhedral results for a vehicle routing problem, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, On symmetric subtour problems, Clique tree inequalities define facets of the asymmetric traveling salesman polytope, Survey of facial results for the traveling salesman polytope, The skeleton of the symmetric Traveling Salesman Polytope, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, The general routing polyhedron: A unifying framework, Facets and algorithms for capacitated lot sizing, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), The 2-edge-connected subgraph polyhedron, On the symmetric travelling salesman problem II: Lifting theorems and facets, The traveling salesman problem on a graph and some related integer polyhedra, A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks, Polyhedral Combinatorics in Combinatorial Optimization, Some facets of the simple plant location polytope
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Neighbor relations on the convex of cyclic permutations
- On the symmetric travelling salesman problem II: Lifting theorems and facets
- The travelling salesman problem and a class of polyhedra of diameter two
- Partial linear characterizations of the asymmetric travelling salesman polytope
- Lineare Charakterisierungen von Travelling Salesman Problemen
- Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
- Maximum matching and a polyhedron with 0,1-vertices
- The Two-Triangle Case of the Acquaintance Graph
- Edmonds polytopes and weakly hamiltonian graphs
- A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM
