The symmetric quadratic traveling salesman problem

DOI10.1007/s10107-012-0568-1zbMath1282.90243OpenAlexW2072484718MaRDI QIDQ2434982

Anja Fischer, Christoph Helmberg

Publication date: 3 February 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-012-0568-1

zbMATH Keywords

combinatorial optimizationquadratic 0-1 programmingreload cost modelangular-metric traveling salesman problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Minimization and maximization versions of the quadratic travelling salesman problem, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, Inductive linearization for binary quadratic programs with linear constraints, The multi-stripe travelling salesman problem, A tabu search with geometry‐based sparsification methods for angular traveling salesman problems, An extended approach for lifting clique tree inequalities, Linear models and computational experiments for the quadratic TSP, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, 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, Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure, A Polyhedral Study of the Quadratic Traveling Salesman Problem, Matroid optimization problems with monotone monomials in the objective, Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times, A class of exponential neighbourhoods for the quadratic travelling salesman problem

Uses Software

• SCIP
• CPLEX
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SCIP: solving constraint integer programs
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• The minimum reload \(s-t\) path, trail and walk problems
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The traveling salesman problem and its variations
• A combinatorial algorithm for weighted stable sets in bipartite graphs
• On Minimum Reload Cost Cycle Cover
• On minimum reload cost paths, tours, and flows
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Lineare Charakterisierungen von Travelling Salesman Problemen
• The Angular-Metric Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• Edmonds polytopes and weakly hamiltonian graphs