Anstreicher, Kurt; Brixius, Nathan; Goux, Jean-Pierre; Linderoth, Jeff Solving large quadratic assignment problems on computational grids. (English) Zbl 1030.90105 Math. Program. 91, No. 3 (B), 563-588 (2002). 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. Cited in 51 Documents MSC: 90C27 Combinatorial optimization 90C09 Boolean programming 90C20 Quadratic programming 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:metacomputing; branch-and-bound algorithm Software:QAPLIB; HTCondor MW; GRASP_QAP; ZRAM; PVM; SUTIL PDFBibTeX XMLCite \textit{K. Anstreicher} et al., Math. Program. 91, No. 3 (B), 563--588 (2002; Zbl 1030.90105) Full Text: DOI