Experiments with LAGRASP heuristic for set k‐covering

Experiments with LAGRASP heuristic for set k‐covering

0.00 Avg rating0 Votes
Article ID: iaor20118051
Volume: 5
Issue: 3
Start Page Number: 407
End Page Number: 419
Publication Date: Aug 2011
Journal: Optimization Letters
Authors: , ,
Keywords: heuristics
Abstract:

The set k‐covering problem (SC k P) 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 SC k P. 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.

Reviews

Required fields are marked *. Your email address will not be published.