Optimization Online


The Asymmetric Quadratic Traveling Salesman Problem

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

Abstract: The quadratic traveling salesman problem asks for a tour of minimal costs where the costs are associated with each two arcs that are traversed in succession. This structure arises, e. g., if the succession of two arcs represents the costs of loading processes in transport networks or a switch between different technologies in communication networks. Based on a quadratic integer program we present a linearized integer programming formulation and study the corresponding polyhedral structure of the asymmetric quadratic traveling salesman problem (AQTSP), where the costs may depend on the direction of traversal. The constructive approach that is used to establish the dimension of the underlying polyhedron allows to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are presented that exclude conflicting configurations. Among these the first one is separable in polynomial time, the separation problem for the second class is NP-complete under certain conditions. We provide a general strengthening approach that allows to lift valid inequalities for the asymmetric traveling salesman problem (ATSP) to stronger valid inequalities for AQTSP. Applying this approach to the subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the (D_3)-, (D_4^-)-, (D_4^+)-inequalities of the ATSP the strengthening approach is not sufficient to obtain a facet. First computational results are presented to illustrate the importance of the new inequalities. In particular, with these inequalities the running times can be improved for some real-world instances from biology by orders of magnitude in comparison to other state of the art methods in the literature.

Keywords: combinatorial optimization, polyhedral combinatorics, quadratic 0-1 programming, 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-19, Fakultaet für Mathematik, Technische Universitaet Chemnitz, D-09107 Chemnitz, December 2011

Download: [PDF]

Entry Submitted: 12/12/2011
Entry Accepted: 12/12/2011
Entry Last Modified: 12/12/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