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

Link:
Autor/in:
Erscheinungsjahr:
1988
Medientyp:
Text
Schlagworte:
  • Travelling salesman problem
  • cutting planes
  • facets
  • polyhedron
Beschreibung:
  • A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known "comb inequalities", the "path inequalities" and the "3-star constraints" as special cases. Its relation to the "clique tree inequalities" is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and-under certain conditions-to define facets of the polyhedron associated with this problem. © 1988 The Mathematical Programming Society, Inc.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/c351d043-94b6-4c92-ab5d-3e6a0f740685