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

fYear

2011

fDate

16-20 May 2011

Firstpage

1940

Lastpage

1949

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on

Conference_Location

Shanghai

ISSN

1530-2075

Print_ISBN

978-1-61284-425-1

Electronic_ISBN

1530-2075

Type

conf

DOI

10.1109/IPDPS.2011.354

Filename

6009068