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

DOI10.1007/BF01580734zbMath0652.90072MaRDI QIDQ1107441

Bernhard Fleischmann

Publication date: 1988

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

zbMATH Keywords

valid inequalitiesfacetsgraphical travelling salesman polytopestar-constraints

Mathematics Subject Classification ID

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

Related Items

A polyhedral approach to the rural postman problem, Routing problems: A bibliography, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, 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, Polyhedral study of the capacitated vehicle routing problem, Branch and cut methods for network optimization, Certification of an optimal TSP tour through 85,900 cities, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, The general routing polyhedron: A unifying framework, The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra, The traveling salesman problem on a graph and some related integer polyhedra, Survey of facial results for the traveling salesman polytope

Cites Work

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