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

Link:

https://doi.org/10.1007/bf01580734

Autor/in:

Fleischmann, Bernhard

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