Restart strategies for GRASP with path-relinking heuristics

M.G.C. Resende and C.C. Ribeiro

Optimization Letters, vol. 5, pp. 467-478,  2011.


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.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified:  21 October 2011

Copyright Notice