|
|
MW-QAP
Quadratic Assignment Problem on Metacomputing Platforms.
Kurt Anstreicher, Nathan Brixius, Jean-Pierre Goux, and Jeff Linderoth
Despite its simple statement - minimize the assignment cost of n
facilities to n locations - it is extremely difficult to solve even
modest instances of this problem. Problems with n>20 are difficult;
problems with n>30 have not even been attempted yet. The metacomputing
paradigm has emerged as an economical way to harness the power of
large, distributed collections of computers, making use of compute
cycles that would otherwise be wasted. By embedding a new relaxation
technique into a branch-and-bound framework, and implementing the
resulting solver to run in parallel on such platforms, we hold the
world record for the QAP challenge. Our methodology will be described
including branching/bounding strategies as well as parallel
implementation details. We currently hold the world record in solving
QAP instances. Our goal now is to
solve NUG30, an unsolved problem formulated 30 years ago.
 And we did it!!! We solved NUG30
to optimality, check the NUG30 Web Site for
more details.
For stories of our eralier success you can read about the
More on QAP :
|
