Computing compatible tours for the symmetric traveling salesman problem

DOI10.1007/s12532-010-0021-5zbMath1279.90144OpenAlexW2102792606WikidataQ57702184 ScholiaQ57702184MaRDI QIDQ542055

Klaus M. Wenger, Andrea Lodi, Adam N. Letchford, Matteo Fortini

Publication date: 8 June 2011

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/45768/1/10.pdf

zbMATH Keywords

heuristicstraveling salesman problembranch-and-cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Uses Software

• TSPLIB
• LKH
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimizing over the subtour polytope of the travelling salesman problem
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• Some simplified NP-complete graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The traveling salesman problem and its variations
• Worst-case comparison of valid inequalities for the TSP
• Good triangulations yield good tours
• The Travelling Salesman and the PQ-Tree
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• TSPLIB—A Traveling Salesman Problem Library
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP