Lineare Charakterisierungen von Travelling Salesman Problemen

DOI10.1007/BF01918456zbMath0348.90147OpenAlexW1998736169MaRDI QIDQ4119037

Manfred W. Padberg, Martin Grötschel

Publication date: 1977

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01918456

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Polytopes and polyhedra (52Bxx)

Related Items

A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets, A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks, On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets, The symmetric quadratic traveling salesman problem, An extended approach for lifting clique tree inequalities, The facets of the asymmetric 5-city traveling salesman polytope, Partial linear characterizations of the asymmetric travelling salesman polytope, On the symmetric travelling salesman problem I: Inequalities, A spectral approach to polyhedral dimension, The optimum assignments and a new heuristic approach for the traveling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edmonds polytopes and a hierarchy of combinatorial problems
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• The travelling salesman problem and a class of polyhedra of diameter two
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• On the facial structure of set packing polyhedra
• Paths, Trees, and Flowers
• The Traveling Salesman Problem: A Survey
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• A Remark on “an Inequality for the Number of Lattice Points in a Simplex”
• On the Set-Covering Problem
• Edmonds polytopes and weakly hamiltonian graphs