A parallel branch and bound algorithm for the quadratic assignment problem
type: Item
instance of: scholarly article
title: A parallel branch and bound algorithm for the quadratic assignment problem
zbMATH Open document ID: 0632.90047
DOI: 10.1016/0166-218X(87)90022-9
author: Catherine Roucairol
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: We propose a parallel branch and bound algorithm for the quadratic assignment problem; this algorithm has been implemented on an asynchronous multiprocessor machine with shared memory (the Cray X-MP). For problems with size \(n\geq 10\), the improvement in using n processors is very close to n, and moreover very good results are obtained for a classical example from the literature with size 12.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 4029260
zbMATH Keywords: parallel branch and bound
zbMATH Keywords: quadratic assignment
zbMATH Keywords: asynchronous multiprocessor machine
MaRDI profile type: Publication
cites work: Q3696856
cites work: Branching from the largest upper bound. Folklore and facts
cites work: Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
cites work: Experiments with parallel algorithms for combinatorial problems
cites work: Q3050144
cites work: Anomalies in parallel branch-and-bound algorithms
cites work: MANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
Wikidata QID: Q128132087
description: scientific article; zbMATH DE number 4029260