Talk abstract:
Using parallelism to push the limits of solvable Quadratic
Assignment Problem instances--is Nugent 30 within reach?
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.
Back to Workshop
Schedule
1996-1997
Mathematics in High Performance Computing
|
