Solving large quadratic assignment problems on computational grids

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 computat...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2002-02, Vol.91 (3), p.563-588
Main Authors: ANSTREICHER, Kurt, BRIXIUS, Nathan, GOUX, Jean-Pierre, LINDEROTH, Jeff
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assignment problem
Distributed processing
Eigenvalues
Exact sciences and technology
Linear programming
Mathematical programming
Operational research and scientific management
Operational research. Management science
Optimization
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s101070100255