A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

DOI10.1007/BF01581188zbMath0758.90075OpenAlexW1974443370MaRDI QIDQ1194853

Joseph F. Pekny, Donald L. Miller

Publication date: 6 October 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581188

zbMATH Keywords

parallel branch-and-bound algorithmasymmetric traveling salesmanlower bounding technique subtour elimination

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Parallel numerical computation (65Y05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (13)

A distributed exact algorithm for the multiple resource constrained sequencing problem ⋮ A branch-and-cut algorithm for vehicle routing problems ⋮ Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs ⋮ On the exact solution of the no-wait flow shop problem with due date constraints ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ Routing problems: A bibliography ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ Solution of large dense transportation problems using a parallel primal algorithm ⋮ A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem ⋮ On the Use of a Mixed Integer Non-linear Programming Model for Refrigerant Design ⋮ Parallel processing for difficult combinatorial optimization problems ⋮ An application of parallel virtual machine framework to film production problem ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Primal-dual algorithms for the assignment problem
• 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
• Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem
• Anomalies in parallel branch-and-bound algorithms
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Some Examples of Difficult Traveling Salesman Problems
• A parallel shortest augmenting path algorithm for the assignment problem
• An Algorithm for the Traveling Salesman Problem

This page was built for publication: A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems