The symmetric quadratic traveling salesman problem

DOI10.1007/S10107-012-0568-1MaRDI QIDQ2434982zbMATH OpenOpenAlexFDO

Authors 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

angular-metric traveling salesman problemcombinatorial optimizationquadratic 0-1 programmingreload cost model

Mathematics Subject Classification ID

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

Recommendations

• An analysis of the asymmetric quadratic traveling salesman polytope
• A polyhedral study of the quadratic traveling salesman problem
• An extended approach for lifting clique tree inequalities
• A new class of cutting planes for the symmetric travelling salesman problem
• Linear models and computational experiments for the quadratic TSP

Cites work

• A combinatorial algorithm for weighted stable sets in bipartite graphs
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Edmonds polytopes and weakly hamiltonian graphs
• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 714530 (Why is no real title available?)
• scientific article; zbMATH DE number 2152071 (Why is no real title available?)
• scientific article; zbMATH DE number 1420900 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Lineare Charakterisierungen von Travelling Salesman Problemen
• On minimum reload cost cycle cover
• On minimum reload cost paths, tours, and flows
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• SCIP: solving constraint integer programs
• Solution of a Large-Scale Traveling-Salesman Problem
• The Angular-Metric Traveling Salesman Problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The minimum reload \(s-t\) path, trail and walk problems
• The traveling salesman problem and its variations
• The traveling salesman problem. A computational study.
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem

Cited in

(21)

• The multi-stripe travelling salesman problem
• 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
• The maximum travelling salesman problem on symmetric Demidenko matrices
• Geometric and LP-based heuristics for angular travelling salesman problems in the plane
• Matroid optimization problems with monotone monomials in the objective
• Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
• Exact and heuristic algorithms for capacitated vehicle routing problems with quadratic costs structure
• A polyhedral study of the quadratic traveling salesman problem
• Lower bounding procedure for the asymmetric quadratic traveling salesman problem
• scientific article; zbMATH DE number 1342125 (Why is no real title available?)
• An analysis of the asymmetric quadratic traveling salesman polytope
• An extended approach for lifting clique tree inequalities
• Branch-price-and-cut algorithms for the vehicle routing problem with stochastic and correlated travel times
• Linear models and computational experiments for the quadratic TSP
• Minimization and maximization versions of the quadratic travelling salesman problem
• Inductive linearization for binary quadratic programs with linear constraints
• A tabu search with geometry‐based sparsification methods for angular traveling salesman problems
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• A class of exponential neighbourhoods for the quadratic travelling salesman problem

Describes a project that uses

Uses Software

• SCIP
• Concorde
• CPLEX

This page was built for publication: The symmetric quadratic traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434982)