L.S. Pessoa, M. G. C. Resende, and C.C. Ribeiro
Submitted to Matheuristics 2010.
ABSTRACT
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.
Last modified: 10 March 2010