  


The Symmetric Quadratic Traveling Salesman Problem
Anja Fischer(anja.fischermathematik.tuchemnitz.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 NPcomplete. 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 01 programming, angularmetric traveling salesman problem, reload cost model Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming (01 Programming ) Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Preprint 20118, Fakultät für Mathematik, Technische Universität Chemnitz, D09107 Chemnitz, April 2011 Download: [PDF] Entry Submitted: 04/27/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  