Change search
ReferencesLink to record
Permanent link

Direct link
Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Show others and affiliations
2014 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, Vol. 166, 97-114 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2014. Vol. 166, 97-114 p.
Keyword [en]
Traveling Salesman Problem, Branch-and-bound, Branch-and-cut, Heuristical methods, Exact methods, Bioinformatics
National Category
Computer and Information Science Mathematics
URN: urn:nbn:se:umu:diva-88325DOI: 10.1016/j.dam.2013.09.011ISI: 000332434400010OAI: diva2:725520
Available from: 2014-06-16 Created: 2014-04-30 Last updated: 2015-05-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Applied Mathematics
Computer and Information ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 78 hits
ReferencesLink to record
Permanent link

Direct link