A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
From MaRDI portal
Publication:1158108
DOI10.1016/0377-2217(82)90015-7zbMath0471.90088OpenAlexW1995274002MaRDI QIDQ1158108
Publication date: 1982
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(82)90015-7
computational resultsbranch and bound algorithmheuristic solutions1-tree relaxationsymmetric traveling salesmanLagrangean approach
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05)
Related Items
Sensitivity analysis for symmetric 2-peripatetic salesman problems, Edge exchanges in the degree-constrained minimum spanning tree problem, TSP race: minimizing completion time in time-sensitive applications, A simulation tool for the performance evaluation of parallel branch and bound algorithms, Efficient optimization of the Held-Karp lower bound, Bounds for the symmetric 2-peripatetic salesman problem, A branch-and-bound algorithm for the singly constrained assignment problem, Exact hybrid algorithms for solving a bi-objective vehicle routing problem, The symmetric travelling salesman problem. II: New low bounds, A discrete cross aisle design model for order-picking warehouses, Identification of non-optimal arcs for the traveling salesman problem, The symmetric traveling salesman problem and edge exchanges in minimal 1- trees, Coarse-Graining Large Search Landscapes Using Massive Edge Collapse, Travelling salesman problem tools for microcomputers, The traveling salesman problem: An overview of exact and approximate algorithms, Iterative state-space reduction for flexible computation, An efficient heuristic algorithm for the bottleneck traveling salesman problem, A note on relatives to the Held and Karp 1-tree problem, Symmetric traveling salesman problems, Optimizing tabu list size for the traveling salesman problem, A framework for multi-robot node coverage in sensor networks, Stability aspects of the traveling salesman problem based on \(k\)-best solutions, The symmetric clustered traveling salesman problem, New lower bounds for the symmetric travelling salesman problem, Estimating the Held-Karp lower bound for the geometric TSP, An empirical study of a new metaheuristic for the traveling salesman problem, A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex, Lower bounding techniques for frequency assignment, Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem, Improving heuristics for the frequency assignment problem, An effective implementation of the Lin-Kernighan traveling salesman heuristic, A useful transform of standard input data for a classical NP-complete problem, A branch and bound algorithm for symmetric 2-peripatetic salesman problems, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A Dynamic Programming Approach to Sequencing Problems
- Validation of subgradient optimization
- Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
- Computer Solutions of the Traveling Salesman Problem
- The Shortest Hamiltonian Chain of a Graph
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II