The graphical relaxation: A new framework for the symmetric traveling salesman polytope

DOI10.1007/BF01581259zbMath0780.90103OpenAlexW1964127155WikidataQ58002939 ScholiaQ58002939MaRDI QIDQ1803616

Denis Naddef, Giovanni Rinaldi

Publication date: 29 June 1993

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

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

zbMATH Keywords

facet-defining inequalitiespolyhedronlinear inequalitylifting theoremsgraphical relaxationcomposition of inequalitiessymmetric traveling salesman polytope

Mathematics Subject Classification ID

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

Related Items

Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem, The pickup and delivery problem: Faces and branch-and-cut algorithm, Multi-depot multiple TSP: a polyhedral study and computational results, On the graphical relaxation of the symmetric traveling salesman polytope, Upgrading edges in the graphical TSP, Facet Generating Techniques, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), Generating partitions of a graph into a fixed number of minimum weight cuts, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time, On the general routing polytope, Computing finest mincut partitions of a graph and application to routing problems, Traveling salesman path problems, A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone, New facets of the STS polytope generated from known facets of the ATS polytope, DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES, Hamiltonian path and symmetric travelling salesman polytopes, The general routing polyhedron: A unifying framework, Combinatorial optimization and small polytopes, New inequalities for the general routing problem, The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra, On the facets and diameter of thek-cycle polytope, On the facial structure of symmetric and graphical traveling salesman polyhedra, The 2-edge-connected subgraph polyhedron, Survey of facial results for the traveling salesman polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solution of large-scale symmetric travelling salesman problems
• Facet identification for the symmetric traveling salesman polytope
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• A complete description of the traveling salesman polytope on 8 nodes
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• 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
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The traveling salesman problem on a graph and some related integer polyhedra
• On the symmetric travelling salesman problem: A computational study
• Small Travelling Salesman Polytopes
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices
• Edmonds polytopes and weakly hamiltonian graphs