Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Anja Fischer, Christoph Helmberg: The Symmetric Quadratic Traveling Salesman Problem

Anja Fischer, Christoph Helmberg: The Symmetric Quadratic Traveling Salesman Problem

Anja Fischer
Christoph Helmberg
The Symmetric Quadratic Traveling Salesman Problem
Electronic source:
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 08, 2011
Mathematics Subject Classification:
90C57 []
90C27 []
90C09 []
In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. First computational results are presented to illustrate the importance of the new inequalities.
combinatorial optimization, quadratic 0-1 programming, angular-metric traveling salesman problem, reload cost model
Publication time:


  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …

  • Ganz großer Sport

    Wer sind die besten Sportlerinnen und Sportler der TU Chemnitz 2017 – Wahl gab Aufschluss, eine Sportlerin schaffte den dritten Sieg in Folge …