A Design of a GPU Based Solver for Quadratic Assignment Problems

Many real-world allocation problems can be formulated as quadratic assignment problems (QAPs) that are NP-hard and lack polynomial-time approximations. While several heuristic algorithms have been developed, no clear and general solution method has been devised to date. In fact, the solution quality and runtime fluctuate depending on the QAP instances to be solved. We introduce a GPU (graphics processing unit)-based method to solve QAPs. A novel scalable softmax function is designed to generate a two-dimensional assignment matrix in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O$</tex> time with parallelization, where n is the problem size. Owing to recent advancements in GPUs, our method shows shorter runtime with similar solution quality when compared with the best existing algorithms.