A Parallel Exact Solver for the Three-Index Quadratic Assignment Problem
François Galea, Bertrand Le Cun · 2011
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.