Paper Info
Title
Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics.
Abstract
In this paper we introduce an extension of the Traveling Salesman Problem ( TSP ), which is motivated by an important application in bioinformatics. In contrast to the TSP the costs do not only depend on each pair of two nodes traversed in succession in a cycle but on each triple of nodes traversed in succession. This problem can be formulated as optimizing a quadratic objective function over the traveling salesman polytope, so we call the combinatorial optimization problem quadratic TSP ( QTSP ). Besides its application in bioinformatics, the QTSP is a generalization of the Angular-Metric TSP and the TSP with reload costs. Apart from the TSP with quadratic cost structure we also consider the related Cycle Cover Problem with quadratic objective function ( QCCP ). In this work we present three exact solution approaches and several heuristics for the QTSP . The first exact approach is based on a polynomial transformation to a TSP , which is then solved by standard software. The second one is a branch-and-bound algorithm that relies on combinatorial bounds. The best exact algorithm is a branch-and-cut approach based on an integer programming formulation with problem-specific cutting planes. All heuristical approaches are extensions of classic heuristics for the TSP . Finally, we compare all algorithms on real-world instances from bioinformatics and on randomly generated instances. In these tests, the branch-and-cut approach turned out to be superior for solving the real-world instances from bioinformatics. Instances with up to 100 nodes could be solved to optimality in about ten minutes.
Year
DOI
Venue
2014
10.1016/j.dam.2013.09.011
Discrete Applied Mathematics
Keywords
Field
DocType
exact approach,real-world instance,heuristical approach,exact algorithm,exact solution approach,branch-and-cut approach,quadratic cost structure,angular-metric tsp,salesman problem,quadratic objective function,combinatorial optimization problem quadratic,computer and information science,branch and bound,mathematics,branch and cut,traveling salesman problem,bioinformatics
Bottleneck traveling salesman problem,Heuristics,Travelling salesman problem,Integer programming,Combinatorics,Branch and bound,Mathematical optimization,Exact algorithm,Branch and cut,Quadratic equation,Algorithm,Bioinformatics,Mathematics
Journal
Volume
Issue
ISSN
166
C
0166-218X
Citations 
PageRank 
References 
10
0.53
24
Authors
6
Name
Order
Citations
PageRank
A. Fischer1100.53
F. Fischer2100.53
G. Jäger3111.24
J. Keilwagen411010.26
P. Molitor521118.50
I Grosse6141.02