𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A parallel branch-and-bound algorithm for integer linear programming and its implementation on a distributed multiprocessor

✍ Scribed by Atsuko Ikegami; Katsuhiro Aoyagi; Hajime Iizuka

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
830 KB
Volume
24
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper describes a parallel branch‐and‐bound algorithm for general integer linear programming problems and its implementation on a distributed memory multiprocessor nCUBE2.

With a branch‐and‐bound algorithm, the amount of computation on each search tree node varies, and in general, is large. This has led to development of an effective communication strategy for the algorithm presented herein. Its implementation and performance evaluation also are described.

The results show that the more difficult the problem instances become in terms of time to solve on a sequential computer, the more efficient the algorithm presented here proves to be.

πŸ“œ SIMILAR VOLUMES

Performance of a benchmark parallel impl
Performance of a benchmark parallel implementation of the Van Slyke and Wets algorithm for two-stage stochastic programs on the Sequent/Balance
✍ Ariyawansa, K. A. ;Hudson, D. D. πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 1015 KB

We describe a benchmark parallel version of the Van Slyke and Wets (1969) algorithm for two-stage stochastic programs and an implementation of that algorithm on the Sequent/Balance. We also report results of a numerical experiment using random test problems and our implementation. These performance