Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory
INFORMS Journal on Computing · 1999 · Volume 11 · Issue 2
Abstract
Multistart constructive approaches operate by applying a local search procedure to start from different initial solutions produced by a repeated (variable) constructive process. The classical Random Restart procedure and the more recent GRASP procedure are prominent examples of such approaches. Adaptive memory strategies that are the heart of tabu search methods give a foundation for alternative, enhanced, multistart approaches. We demonstrate this by showing that a simple implementation of adaptive memory search principles, even when restricted to the constructive phases, can provide more effective multistart methods. Computational experiments for the quadratic assignment problem disclose that these methods improve significantly over previous multistart methods that do not incorporate such memory based strategies.
Keywords
combinatorial optimization, tabu search, multistart strategy, quadratic assignment problem
Enable JavaScript for citation tools and additional paper interactions.