A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering

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

Submitted to Matheuristics 2010.


The set K-covering problem is an extension of the set covering problem, in which each object has to be covered at least K times. We describe a GRASP with path-relinking heuristic for its solution, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain solutions for the Lagrangean relaxation problem. Numerical experiments have shown that the Lagrangean heuristics performed consistently better than GRASP. The GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions even after the stabilization of the lower bounds. 

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 10 March 2010

Copyright Notice