The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n >= 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solutions of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 problems, is reported.
Citation
submitted to Mathematical Programming.
Article
View Solving Large Quadratic Assignment Problems on Computational Grids