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

DOI10.1007/BF01580734MaRDI QIDQ1107441zbMATHFDO

Authors Bernhard Fleischmann

Publication date 1988

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

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)

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

Cites work

• scientific article; zbMATH DE number 3779123 (Why is no real title available?)
• A Cutting Planes Algorithm for the m-Salesmen Problem
• A cutting plane procedure for the travelling salesman problem on road networks
• A note on finding a shortest complete cycle in an undirected graph
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• Distance conserving reductions for nonoriented networks
• Heuristic analysis, linear programming and branch and bound
• On the symmetric travelling salesman problem I: Inequalities
• 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
• The traveling salesman problem on a graph and some related integer polyhedra
• Using cutting planes to solve the symmetric Travelling Salesman problem

Cited in

(21)

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

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)