A Surprisal-Based Greedy Heuristic for the Set Covering Problem

In this paper we exploit concepts from Information Theory to improve the classical Chvatal’s greedy algorithm for the Set Covering Problem. In particular, we develop a new greedy procedure, called Surprisal-Based Greedy Heuristic (SBH), incorporating the computation of a “surprisal” measure when selecting the solution columns. Computational experiments, performed on instances from the OR-Library, show that SBH yields a 2.5% improvement in terms of the objective function value over the Chvatal’s algorithm while retaining similar execution times, making it suitable for real-time applications. The new heuristic was also compared with Kordalewski’s greedy algorithm, obtaining similar solutions with much lower times on large instances, and Grossmann and Wool’s algorithm for unicost instances, where SBH obtained better solutions.