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

DOI10.1007/BF01581259MaRDI QIDQ1803616zbMATH OpenOpenAlexWikidataFDO

Authors Denis Naddef, G. 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

polyhedronlinear inequalityfacet-defining inequalitieslifting 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)

Recommendations

• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• On the graphical relaxation of the symmetric traveling salesman polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• scientific article; zbMATH DE number 3943559
• On the facial structure of symmetric and graphical traveling salesman polyhedra

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3943559 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3495892 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• A complete description of the traveling salesman polytope on 8 nodes
• A new class of cutting planes for the symmetric travelling salesman problem
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• Edmonds polytopes and weakly hamiltonian graphs
• Facet identification for the symmetric traveling salesman polytope
• Maximum matching and a polyhedron with 0,1-vertices
• On the facial structure of set packing polyhedra
• 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
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Small Travelling Salesman Polytopes
• Solution of large-scale symmetric travelling salesman problems
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem on a graph and some related integer polyhedra

Cited in

(29)

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

This page was built for publication: The graphical relaxation: A new framework for the symmetric traveling salesman polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803616)