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

DOI10.1007/BF01581259zbMATH Open0780.90103OpenAlexW1964127155WikidataQ58002939 ScholiaQ58002939MaRDI QIDQ1803616FDOQ1803616

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• 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
• Title not available (Why is that?)
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices
• Title not available (Why is that?)
• Facet identification for the symmetric traveling salesman polytope
• Solution of large-scale symmetric travelling salesman problems
• Edmonds polytopes and weakly hamiltonian graphs
• A complete description of the traveling salesman polytope on 8 nodes
• On the symmetric travelling salesman problem: A computational study
• 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
• Small Travelling Salesman Polytopes
• Title not available (Why is that?)
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope

Cited In (29)

• Heuristic algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
• Hamiltonian path and symmetric travelling salesman polytopes
• New facets of the STS polytope generated from known facets of the ATS polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• 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
• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• The general routing polyhedron: A unifying framework
• Not Every GTSP Facet Induces an STSP Facet
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• 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
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation

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)