Experiments with LAGRASP heuristic for set k-covering

L.S. Pessoa, M.G.C. Resende, and C.C. Ribeiro

Optimization Letters, vol. 5, pp. 407-419, 2011.


The set k-covering problem is a variant of the classical set covering problem, in which each object is required to be covered at least k times. We describe a hybrid Lagrangean heuristic, named LAGRASP, which combines subgradient optimization and GRASP with path-relinking to solve the set k-covering problem. Computational experiments carried out on 135 test instances show experimentally that by properly tuning the parameters of LAGRASP, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, LAGRASP makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, whereas other strategies fail to find new improving solutions.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 21 October 2011

Copyright Notice