A Parallel Computational Framework for Solving Quadratic Assignment Problems Exactly

The Quadratic Assignment Problem (QAP) is a combinatorial opti-mization problem used to model a number of different engineering ap-plications. Originally it was the problem of optimally placing electronic components to minimize wire length. However, essentially the same prob-lem occurs in backboard and circuit wiring and testing, facility layout, ur-ban planning, ergonomics, scheduling, and generally in location problems. Additionally, it is one of the the most computationally difficult combina-torial problems known. For example, a recent solution of a problem of size thirty using a state-of-the-art solver took the equivalent of 7 single-CPU years. The goal of this project was to create an open and easily extensi-ble parallel framework for solving the QAP exactly. This framework has shown good scalability to many cores. It experimentally has over 95 % ef-ficiency when run on a system with 24 cores. This framework is designed to be modular to allow for the addition of different initial heuristics and lower bounds. The framework was tested with many heuristics including a new gradient projection heuristic and a simulated annealing procedure. The framework was also tested with different lower bounds including the Gilmore-Lawler bound (GLB). The GLB was computed using a custom implementation of the Kuhn-Munkres algorithm to solve the associated linear assignment problem (LAP). The core backtracking solver uses the unique approach of only considering partial solutions rather than recur-sively solving sub-problems. This allows for more efficient parallelization as inter-process communication is kept to a minimum.