A simulation tool for the performance evaluation of parallel branch and bound algorithms |
| |
Authors: | Arie de Bruin Alexander H. G. Rinnooy Kan Harry W. J. M. Trienekens |
| |
Affiliation: | (1) Erasmus University, 3000 DR, P.O. Box 1738, Rotterdam, The Netherlands |
| |
Abstract: | Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm. |
| |
Keywords: | 90C27 68Q10 68R05 |
本文献已被 SpringerLink 等数据库收录! |
|