Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory

Multistart constructive approaches operate by applying a local search proce dure to start from different initial solutions produced by a repeated (vari able) constructive process. The classical Random Restart procedure and the more recent GRASP procedure are prominent examples of such approaches. Adap tive memory strategies that are the heart of tabu search methods give a fou ndation for alternative, enhanced, multistart approaches. We demonstrate th is by showing that a simple implementation of adaptive memory search princi ples, even when restricted to the constructive phases, can provide more eff ective multistart methods. Computational experiments for the quadratic assi gnment problem disclose that these methods Improve significantly over previ ous multistart methods that do not incorporate such memory based strategies .