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.
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.
of full paper
Resende's Home Page
Last modified: 10 March 2010