A Parallel Exact Solver for the Three-Index Quadratic Assignment Problem

摘要

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.