Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics

DOI10.1016/j.dam.2013.09.011zbMath1288.90074OpenAlexW2120983471MaRDI QIDQ2636833

Yanyan Li

Publication date: 18 February 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.09.011

zbMATH Keywords

branch-and-boundtraveling salesman problembioinformaticsbranch-and-cutexact methodsheuristical methods

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Related Items

Minimization and maximization versions of the quadratic travelling salesman problem, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning, The quadratic cycle cover problem: special cases and efficient bounds, A tabu search with geometry‐based sparsification methods for angular traveling salesman problems, Unnamed Item, A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions, Geometric and LP-based heuristics for angular travelling salesman problems in the plane, Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs, A class of exponential neighbourhoods for the quadratic travelling salesman problem, Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems

Uses Software

• CPLEX
• LKH
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transforming asymmetric into symmetric traveling salesman problems
• Solution of large-scale symmetric travelling salesman problems
• Certification of an optimal TSP tour through 85,900 cities
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• On the quadratic assignment problem
• An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs
• Geometric algorithms and combinatorial optimization.
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• The traveling salesman problem and its variations
• When the greedy algorithm fails
• Discrete optimization methods to determine trajectories for Dubins' vehicles
• On minimum reload cost paths, tours, and flows
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Tolerance-based Algorithms for the Traveling Salesman Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• The Angular-Metric Traveling Salesman Problem
• Traveling Salesperson Problems for the Dubins Vehicle
• Solution of a Large-Scale Traveling-Salesman Problem
• Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP
• Some Basics on Tolerances
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Construction heuristics for the asymmetric TSP.