Simple Lagrangian heuristic for the set covering problem

In this paper a simple Lagrangian heuristic is proposed for the set covering problem. It is based on simple and classical ideas: Lagrangian duality, greedy heuristic for the set covering problem, subgradient optimization and redundant covers. The main interesting point of the paper lies in the fact that the proposed heuristic turns out to be efficient for low density set covering problems with a large number of variables.