Optimization Online


Solving Large Quadratic Assignment Problems on Computational Grids

Kurt Anstreicher (kurt-anstreicher***at***uiowa.edu)
Nathan Brixius (natbr***at***microsoft.com)
Jean-Pierre Goux (jean-pierre.goux***at***artelys.com)
Jeff Linderoth ( jlinderoth***at***dashopt.com)

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

Keywords: Quadratic assignment problem - branch and bound - computational grid - metacomputing - convex relaxation

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: submitted to Mathematical Programming.

Download: [Postscript]

Entry Submitted: 10/27/2000
Entry Accepted: 10/27/2000
Entry Last Modified: 10/31/2000

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society