Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem

DOI10.1016/0167-6377(89)90038-2zbMath0668.90089OpenAlexW2006054213MaRDI QIDQ1118534

Joseph F. Pekny, Donald L. Miller

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90038-2

zbMATH Keywords

assignment problemsubtour eliminationparallel branch-and-bound algorithmasymmetric traveling salesmanlower bounding technique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Theory of operating systems (68N25)

Related Items

A TSSP+1 decomposition strategy for the vehicle routing problem, SelfSplit parallelization for mixed-integer linear programming, Routing problems: A bibliography, Parameter tuning for a cooperative parallel implementation of process-network synthesis algorithms, Solution of large dense transportation problems using a parallel primal algorithm, Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem, A distributed computation algorithm for solving portfolio problems with integer variables, Optimality conditions to the acyclic travelling salesman problem., The traveling salesman problem: An overview of exact and approximate algorithms, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, New edges not used in shortest tours of TSP, Experiments with parallel branch-and-bound algorithms for the set covering problem, A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solution of large dense transportation problems using a parallel primal algorithm
• Branch-and-bound and parallel computation: A historical note
• A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions
• A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems
• The auction algorithm: A distributed relaxation method for the assignment problem
• Performance of parallel branch-and-bound algorithms
• Anomalies in parallel branch-and-bound algorithms
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• An Algorithm for the Traveling Salesman Problem
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The traveling-salesman problem and minimum spanning trees: Part II