×

Solving large quadratic assignment problems on computational grids. (English) Zbl 1030.90105

Summary: 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.

MSC:

90C27 Combinatorial optimization
90C09 Boolean programming
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI