
Experiments with Parallel Algorithms for Combinatorial Problems
G.A.P. Kindervater
Centre for Mathematics and Computer Science, Amsterdam
H.W.J.M. Trienekens
Erasmus University, Rotterdam
ABSTRACT
In the last decade many models for parallel computation have been proposed and
many parallel algorithms have been developed. However, few of these models have been
realized and most of these algorithms are supposed to run on idealized, unrealistic parallel
machines.
The parallel machines constructed so far all use a simple model of parallel computation.
Therefore, not every existing parallel machine is equally well suited for each type
of algorithm. The adaptation of a certain algorithm to a specific parallel architecture may
severely increase the complexity of the algorithm or severely obscure its essence.
Little is known about the performance of some standard combinatorial algorithms
on existing parallel machines. In this paper we present computational results concerning
the solution of knapsack, shortest paths and changemaking problems by branch and
bound, dynamic programming, and divide and conquer algorithms on the ICLDAP (an
SIMD computer), the Manchester dataflow machine and the CDCCYBER205 (a pipeline
computer).
1980 Mathematics Subject Classification: 90C27, 68Q10, 68R05.
Key Words & Phrases: parallel computer, SIMD, MIMD, pipelining, dataflow, branch and bound, dynamic programming, divide and conquer, knapsack, shortest paths, changemaking.
Note: This paper appeared in European Journal of Operational Research, Vol. 33, pp 65 81, 1988.
1. Introduction
In the last decade computer scientists have proposed many parallel computers, based on various models of computation and architectures. However, so far only a few of these parallel computers have been built, due to today's technical limitations. All existing parallel computers use the easier models of computation and the easier architectures. Therefore these machines are less powerful than the theoretical models.
In the mean time operations researchers have developed many parallel algorithms for combinatorial
problems. Nearly all these algorithms are based on models of parallel computation which are too complicated
to be used in today's parallel computers. As a result, few of these algorithms have actually been
implemented today simply by lack of the parallel computers needed.
hhhhhhhhhhhhhhhhhh
Report 8550/A
Erasmus University Rotterdam, Econometric Institute
P.O. Box 1738, 3000 DR Rotterdam, The Netherlands