Solving Large Quadratic Assignment Problems on Computational Grids
Kurt Anstreicher (kurt-anstreicheruiowa.edu)
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.
Entry Submitted: 10/27/2000
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|