New Exact Methods for Solving Quadratic Traveling Salesman Problem

Abstract

The Quadratic Traveling Salesman Problem (QTSP) is a generalization of the Traveling Salesman Problem (TSP) with important applications in robotics and bioinformatics. The QTSP objective value depends on pairs of consecutive edges in the tour; hence, it is quadratic and generally hard to optimize. While various exact-solving approaches have been explored, many rely on specialized procedures and struggle to scale on large instances. More recently, carefully crafted metaheuristics have demonstrated better primal bounds and scalability, but they cannot provide any guarantees of solution quality nor prove the optimality of any solution. In this work, we propose new exact models for QTSP. We define direct encodings of QTSP in domain-independent dynamic programming (DIDP), constraint programming (CP), mixed integer quadratic programming (MIQP), and mixed integer linear programming (MILP), and compare them with the best-known exact method, a branch and cut (B&C) algorithm, and the state-of-the-art metaheuristic, a hybrid genetic algorithm (HGA). Our experimental results demonstrate that the DIDP model shows better scalability and finds the best feasible solutions on average among all exact solvers, including the B&C algorithm. HGA finds the best feasible solution among all approaches, with DIDP within 15% of the HGA cost on all experimented instances. Also, interestingly, our MILP model with the subtour elimination constraints generally finds better feasible solutions than the B&C algorithm while matching it in proving optimality, suggesting that lazily adding sub-tour elimination cuts is not particularly helpful in QTSP.