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 (11)

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.

This page was built for publication: Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics