Using Parallelism to Push the Limits of Solvable Quadratic Assignment Problem Instances--is Nugent 30 Within Reach?

Wednesday, May 14, 1997 - 9:30am - 10:30am
Vincent 570
Jens Clausen (University of Copenhagen)
At the 14th Mathematical Programming Symposium in 1991, solving Quadratic Assignment Problems of dimension exceeding 15 mentioned as a computational challenge in the introductory remarks. Nevertheless, three years later the solution of a classical benchmark instance, Nugent 20, of dimension 20 was reported, and recently instances of size 24 have been solved. One of the key features in this development has been the use of parallellism in Branch-and-Bound.

The talk will review the recent development regarding the solution of large QAP-instances, discuss the choice of bounding function for a parallel Branch-and-Bound algorithm for QAP, and address the feasibility of pushing the limits of solvable QAP instances by combining new bound calculation functions with high performance parallel computers.

Joint work with Michael Perregaard, Stefan Karisch, Torben Espersen, Ambros Marzetta, Adrian Bruengger, and Stefan Tschoeke.