Title :
A Parallel Exact Solver for the Three-Index Quadratic Assignment Problem
Author :
Galea, François ; Cun, Bertrand Le
Author_Institution :
Embedded Real Time Syst. Lab., CEA, Gif-sur-Yvette, France
Abstract :
Computers with multiple processor cores using shared memory are now ubiquitous. This paper reports an implementation of a branch-and-bound - based exact algorithm for the Three-Index Quadratic Assignment Problem (Q3AP) on multicore processors. Our parallel implementation has two levels of parallelism. The first, the most common parallelizes the tree search procedure using the Bob++ framework. The second one parallelizes the computation of the lower bound using the SIMD instruction set extensions of modern processors.
Keywords :
instruction sets; parallel algorithms; quadratic programming; shared memory systems; tree searching; Bob++ framework; SIMD instruction set extension; branch-and-bound based exact algorithm; multicore processors; multiple processor cores; parallel exact solver; parallel implementation; shared memory; three-index quadratic assignment problem; tree search parallelization; Arrays; Instruction sets; Multicore processing; Parallel processing; Programming environments; Search problems; Software algorithms;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.354
