  


The Asymmetric Quadratic Traveling Salesman Problem
Anja Fischer(anja.fischermathematik.tuchemnitz.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 NPcomplete 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 NPcomplete. 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 realworld 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 01 programming, reload cost model Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming (01 Programming ) Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Preprint 201119, Fakultaet für Mathematik, Technische Universitaet Chemnitz, D09107 Chemnitz, December 2011 Download: [PDF] Entry Submitted: 12/12/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  