Solving large quadratic assignment problems on computational grids

Solving large quadratic assignment problems on computational grids

0.00 Avg rating0 Votes
Article ID: iaor2003764
Country: Germany
Volume: 91
Issue: 3
Start Page Number: 563
End Page Number: 588
Publication Date: Jan 2002
Journal: Mathematical Programming
Authors: , , ,
Keywords: quadratic assignment
Abstract:

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. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported.

Reviews

Required fields are marked *. Your email address will not be published.