Solving large quadratic assignment problems on computational grids |
| |
Authors: | Kurt Anstreicher Nathan Brixius Jean-Pierre Goux Jeff Linderoth |
| |
Institution: | (1) Department of Management Sciences, University of Iowa, Iowa City, IA 52242, USA, e-mail: kurt-anstreicher@uiowa.edu, US;(2) Department of Computer Science, University of Iowa, Iowa City, IA 52242, USA, e-mail: brixius@cs.uiowa.edu, US;(3) Department of Electrical and Computer Engineering, Northwestern University, and Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, Illinois 60439, USA, e-mail: goux@ece.nwu.edu, US;(4) Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, Illinois 60439, USA, e-mail: linderot@mcs.anl.gov, US |
| |
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.
Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001 |
| |
Keywords: | : Quadratic assignment problem – branch and bound – computational grid – metacomputing Mathematics Subject Classification (1991): 90C27 90C09 90C20 |
本文献已被 SpringerLink 等数据库收录! |
|