Branch-and-bound and parallel computation: A historical note
This historical note summarizes what we believe to have been the first use of parallel processing to solve a combinatorial optimization problem by a branch-and-bound algorithm. In 1975, a branch-and-bound algorithm for the traveling salesman problem that used p parallel processors with shared memory was simulated on a single processor. The results show that the simultaneous exploration of several nodes of the search tree yields better feasible solutions earlier. This allows earlier pruning of branches and significantly reduces the number of nodes searched.
- A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions
- A simulation tool for the performance evaluation of parallel branch and bound algorithms
- An Algorithm for the Traveling Salesman Problem
- An introduction to parallelism in combinatorial optimization
- Anomalies in parallel branch-and-bound algorithms
- Branch-and-bound and parallel computation: A historical note
- Experiments with parallel algorithms for combinatorial problems
- scientific article; zbMATH DE number 3889284 (Why is no real title available?)
- MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
- Performance of parallel branch-and-bound algorithms
- Technical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem
- An introduction to parallelism in combinatorial optimization
- Branch-and-bound and parallel computation: A historical note
- Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem
- A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems
- Parallel processing for difficult combinatorial optimization problems
- Parameter tuning for a cooperative parallel implementation of process-network synthesis algorithms
- Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers
- Scheduling experiments on a nulear reactor using mixed integer programming
- Parallel best-first branch-and-bound in discrete optimization: a framework
- Large-scale 0-1 linear programming on distributed workstations
- Transient in a two-DOF nonlinear system
This page was built for publication: Branch-and-bound and parallel computation: A historical note
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099088)
