Optimization Online


The Symmetric Quadratic Traveling Salesman Problem

Anja Fischer(anja.fischer***at***mathematik.tu-chemnitz.de)
Christoph Helmberg(helmberg***at***mathematik.tu-chemnitz.de)

Abstract: 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.

Keywords: combinatorial optimization, quadratic 0-1 programming, angular-metric traveling salesman problem, reload cost model

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Preprint 2011-8, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, April 2011

Download: [PDF]

Entry Submitted: 04/27/2011
Entry Accepted: 04/28/2011
Entry Last Modified: 04/27/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society