A parallel optimal branch-and-bound algorithm for MIN-based multiprocessors

Published 20 January 2003

M.K. Yang, Chita R. Das

DOI10.1109/icpp.1999.797395

Citations1

TL;DR

It is shown that the proposed parallel B&B algorithm performs better than other reported schemes with its various advantageous features such as: less subproblem evaluations, proper load balancing, and limited scope of remote communication through the network.

Abstract

A parallel Optimal Best-First search Branch-and-Bound (B&B) algorithm (obs) is proposed and evaluated for MIN-based multiprocessor systems. The proposed algorithm decomposes a problem into a number of subproblems and each subproblem is processed on a small group of processors. A performance analysis is conducted to estimate the speed-up of the proposed parallel B&B algorithm. It considers both the computation and communication times to evaluate the realistic performance. Simulation data are given, along with analysis results for model validation. It is shown that the proposed algorithm performs better than other reported schemes with its various advantageous features such as: less subproblem evaluations, proper load balancing, and limited scope of remote communication through the network.

Keywords

Computer ScienceEngineering

Operations ResearchBranch-and-Bound Methods: A Survey

1,982 Citations1966Eugene L. Lawler, Derek Wood

The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.

Medical Entomology and ZoologyParallel Computing: Theory and Practice

436 Citations1994Michael J. Quinn

Graph theoretic terminology review of complex numbers parallel algorithm design strategies and how to design parallel algorithms for linear systems and multiprocessors.

International Journal of Parallel ProgrammingParallel depth first search. Part I. Implementation

168 Citations1987V. Nageshwara Rao, Vipin Kumar

A parallel formulation of depth-first search which retains the storage efficiency of sequential depth- first search and can be mapped on to anyMIMD architecture is presented and results show that hypercube and sharedmemory architectures are significantly better.

IEEE Transactions on ComputersMANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems

85 Citations1984Wah, Ma

This paper proposes and analyze the design of MANIP, a parallel machine for processing nondeterministic polynomial (NP)-hard problems, and proposes a system with distributed intelligence so that sorting can be carried out efticiently.

A randomized parallel branch-and-bound procedure

83 Citations1988Richard M. Karp, Yanjun Zhang

A universal randomized method called Local Best-First Search for parallelizing sequential branch-and-bound algorithms that shows that, uniformly on all instances, the execution time of the method is unlikely to exceed a certain inherent lower bound by more than a constant factor.

View PDF

IEEE Transactions on Software EngineeringStochastic Modeling of Branch-and-Bound Algorithms with Best-First Search

43 Citations1985Benjamin W. Wah, Chee Fen Yu

The average memory space required and the average number of subproblems expanded before the process terminates are estimated and it is confirmed that approximations are very effective in reducing the total number of iterations.

IEEE Transactions on ComputersAnalysis and implementation of branch-and-bound algorithms on a hypercube multicomputer

38 Citations1990Michael J. Quinn

Analytical models for the execution time of loosely synchronous and asynchronous parallel branch-and-bound algorithms are presented, and the models are validated with data from the execution of five algorithms that solve the traveling salesperson problem.

International Journal of Parallel ProgrammingA randomized parallel branch-and-bound algorithm

36 Citations1988Virendra K. Janakiram, Edward F. Gehringer +2 more

It is shown that the performance of randomized algorithms is less affected by factors that prevent most parallel deterministic algorithms from attaining their theoretical speedup bounds and reliability is enhanced because the failure of a single processor leads only to degradation, not failure, of the algorithm.

IEEE Transactions on Parallel and Distributed SystemsEvaluation of a parallel branch-and-bound algorithm on a class of multiprocessors

18 Citations1994M.K. Yang, Chita R. Das

For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes.

Proceedings of the International Conference on Parallel ProcessingParallel Depth First Search on the Ring Architecture

18 Citations1988Vipin Kumar, V. Nageshwara Rao +1 more

This paper introduces the concept of iso-efficiency function to characterize the effectiveness of different work distribution schemes, and presents a new work distribution scheme that is better than the work distribution Scheme used by other researchers, and gives good performance even on large rings.