A surrogate heuristic for set covering problems

The purpose of this paper is to present a new heuristic for set covering problems, based upon continuous surrogate relaxations and subgradient optimization. The algorithm combines problem reduction tests, an adequate step size control, and avoids, preliminary sorting in solving the continuous surrogate relaxations. Computational tests for large scale set covering problems (up to 1000 rows and 12 000 columns) indicate better-quality results than algorithms based on Lagrangian relaxations in terms of final solutions and mainly in computer times. Although the solving of a single surrogate optimization problem is slower than a corresponding Lagrangian optimization, the overall performance is almost twice as fast. This is due to the smaller number of iterations which is a result of faster convergence and less oscillation.