Abstract

A parallel branch and bound algorithm is developed for use with MIMD computers to study the efficiency of parallel processors on general integer linear programming problems. The Haldi and IBM test problems and a System Design model are used in the implementation of the algorithm. Initially the algorithm solves the Haldi and IBM test problems on a single processor computer which simulates a multiple processor computer. The algorithm is then implemented on the Denelcor HEP multiprocessor using two of the IBM problems to compare the results of the simulation to the results using an MIMD computer. Finally the algorithm is implemented on the HEP using the System Design model to show a case in which the number of pivots decreases as the number of processes are increased from seven to the process limit of sixteen.

In general, it is shown that super linear efficiency can be achieved using multiple processors.

Department(s)

Computer Science

Comments

This report is substantially the Ph.D. dissertation of the first author, completed July 1985.

Report Number

CSc-85-2

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1985 University of Missouri--Rolla, All rights reserved.

Publication Date

July 1985

Download

Share

 
COinS