M.G.C. Resende and C.C. Ribeiro
Optimization Letters, vol. 5, pp. 467-478, 2011.
ABSTRACT
GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial opti- mization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i(1), i(2), . . .} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algo- rithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.
Last modified: 21 October 2011