Solving Large Quadratic Assignment Problems on Computational Grids

Kurt Anstreicher (kurt-anstreicheruiowa.edu)
Nathan Brixius (natbrmicrosoft.com)
Jean-Pierre Goux (jean-pierre.gouxartelys.com)
Jeff Linderoth ( jlinderothdashopt.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