A simulation tool for the performance evaluation of parallel branch and bound algorithms
type: Item
instance of: scholarly article
title: A simulation tool for the performance evaluation of parallel branch and bound algorithms
zbMATH Open document ID: 0658.90078
DOI: 10.1007/BF01589406
author: Arie de Bruin
author: Harry W. J. M. Trienekens
author: Alexander H. G. Rinnooy Kan
published in: Mathematical Programming. Series A. Series B
publication date: 1988-01-01T00:00:00Z
review text: 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 algorithms 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65C20
zbMATH DE Number: 4076977
zbMATH Keywords: nondeterminism
zbMATH Keywords: asynchronicity
zbMATH Keywords: Parallel computation
zbMATH Keywords: parallel branch and bound
zbMATH Keywords: simulation
describes a project that uses: DPUP
describes a project that uses: Simula 67
MaRDI profile type: Publication
cites work: Computational Efficiency of Approximate Branch-and-Bound Algorithms
cites work: The Power of Dominance Relations in Branch-and-Bound Algorithms
cites work: A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
cites work: Q3221759
cites work: An introduction to parallelism in combinatorial optimization
cites work: Anomalies in parallel branch-and-bound algorithms
cites work: Branch-and-Bound Methods: General Formulation and Properties
cites work: Q3992743
cites work: Random Trees and the Analysis of Branch and Bound Procedures
description: scientific article; zbMATH DE number 4076977