Lower tolerance-based branch and bound algorithms for the ATSP

DOI10.1016/j.cor.2011.04.003zbMath1251.90319OpenAlexW2134248285MaRDI QIDQ1761975

Marcel Turkensteen, Remco Germs, Boris I. Goldengorin

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.04.003

zbMATH Keywords

branch and boundasymmetric traveling salesman problemtolerances

Mathematics Subject Classification ID

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

Related Items

Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem ⋮ New formulations for the elementary shortest-path problem visiting a given set of nodes ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Extending single tolerances to set tolerances ⋮ Efficient computation of tolerances in the weighted independent set problem for trees ⋮ Global tolerances in the problems of combinatorial optimization with an additive objective function ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ The effect of the asymmetry of road transportation networks on the traveling salesman problem ⋮ Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem

Uses Software

• TSPLIB
• LKH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving the Hungarian assignment algorithm
• On the solution of traveling salesman problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Branching rules revisited
• Cut-and-solve: An iterative search strategy for combinatorial optimization problems
• Tolerance-based branch and bound algorithms for the ATSP
• An addendum on: ``Sensitivity analysis of the optimal assignment
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• Exact solution of large-scale, asymmetric traveling salesman problems
• Some Basics on Tolerances
• Graph-Theoretic Concepts in Computer Science