首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号