A new class of cutting planes for the symmetric travelling salesman problem

DOI10.1007/BF01580734zbMATH Open0652.90072MaRDI QIDQ1107441FDOQ1107441

Authors: Bernhard Fleischmann 

Publication date: 1988

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

Recommendations

• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• Symmetric travelling salesman problem. Some new algorithmic possibilities
• New lower bounds for the symmetric travelling salesman problem
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• The symmetric travelling salesman problem. II: New low bounds
• A cutting plane procedure for the travelling salesman problem on road networks
• A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• scientific article; zbMATH DE number 4093179
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems

zbMATH Keywords

facetsvalid inequalitiesgraphical travelling salesman polytopestar-constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polytopes and polyhedra (52Bxx)

Cites Work

• A cutting plane procedure for the travelling salesman problem on road networks
• The traveling salesman problem on a graph and some related integer polyhedra
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• On the symmetric travelling salesman problem I: Inequalities
• A Cutting Planes Algorithm for the m-Salesmen Problem
• Heuristic analysis, linear programming and branch and bound
• On the symmetric travelling salesman problem: A computational study
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Using cutting planes to solve the symmetric Travelling Salesman problem
• Distance conserving reductions for nonoriented networks
• Title not available (Why is that?)
• A note on finding a shortest complete cycle in an undirected graph

Cited In (21)

• Polyhedral study of the capacitated vehicle routing problem
• Hamiltonian path and symmetric travelling salesman polytopes
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• Ailsa H. Land and her 1979 study of the traveling salesman problem: personal reminiscences and historical remarks
• Restricted 2-factor polytopes
• A complete description of the traveling salesman polytope on 8 nodes
• Certification of an optimal TSP tour through 85,900 cities
• Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
• A note on characterizing canonical cuts using geometry
• The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra
• Routing problems: A bibliography
• A polyhedral approach to the rural postman problem
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• Branch and cut methods for network optimization
• The traveling salesman problem on a graph and some related integer polyhedra
• The general routing polyhedron: A unifying framework
• Survey of facial results for the traveling salesman polytope
• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• The symmetric quadratic traveling salesman problem

This page was built for publication: A new class of cutting planes for the symmetric travelling salesman problem

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