# A Surprisal-Based Greedy Heuristic for the Set Covering Problem
## 1 Introduction  
The Set Covering Problem (SCP) is a classical combinatorial optimization problem which, given a collection of elements, aims to find the minimum number of sets that incorporate (cover) all of these elements. More formally, let \(I\) be a set of \(m\) items and \(J=\{S_{1},S_{2},\ldots,S_{n}\}\) a collection of \(n\) subsets of \(I\) where each subset \(S_{j}\) (\(j=1,\ldots,n\)) is associated to a non-negative cost \(c_{j}\). The SCP finds a minimum cost sub-collection of \(J\) that covers all the elements of \(I\) at minimum cost, the cost being defined as the sum of subsets cost. The SCP finds applications in many fields. One of the most important is crew scheduling, where SCP provides a minimum-cost set of crews in order to cover a given set of trips. These problems include airline crew scheduling (see, for example, [PERSON] [1] and [PERSON] [2]) and railway crew scheduling (see, example, [PERSON] [3]). Other applications are the winner determination problem in combinatorial auctions, a class of sales mechanisms ([PERSON] et al. [4]) and vehicle routing ([PERSON] et al. [5], [PERSON] et al. [6] and [PERSON] et al. [7]). The SCP is also relevant in a number of production planning problems, as described by [PERSON] in [8], wherein solving is often required in _real-time_. In addition, it is worth noting that the set covering problem is equivalent to the hitting set problem [9]. Indeed, we can view an instance of set covering as a bipartite graph in which vertices on the left represent the items, whilst vertices on the right represent the sets, and edges represent the inclusion of items in sets. The goal of the hitting set problem is to find a subset with the minimum number of right vertices such that all left vertices are covered. [PERSON] and [PERSON] in [10] have proven that the SCP is NP-hard in the strong sense. Exact algorithms are mostly based on branch-and-bound and branch-and-cut techniques. [PERSON] [11] utilizes sub-gradient optimization in a branch-and-bound framework. [PERSON] and [PERSON] [12] present a procedure based on cutting planes from _conditional bounds_, i.e., valid lower bounds if the constraint set is amended by certain inequalities. [PERSON] [13] introduces an algorithm which blends dual ascent, sub-gradient optimization and linearprogramming. In [14], [PERSON] and [PERSON] incorporate the [13] algorithm into a Lagrangian heuristic. [PERSON] and [PERSON] [15] use continuous heuristics applied to the dual of the linear programming relaxation, obtaining lower bounds for a branch-and-bound algorithm. Finally, we mention [PERSON] and [PERSON] [16] with their procedure based on a dynamic sub-gradient optimization and branch-and-bound. These algorithms were tested on instances involving up to 200 rows and 2000 columns in the case of [PERSON] and [PERSON]'s algorithms and 400 rows and 4000 columns in [13; 14; 16]. Among these algorithms the fastest one is the [PERSON] and [PERSON]'s algorithm, with an average time in the order of 100 s on small instances and 1000 s on the largest ones (on a Cray-1S computer). [PERSON] [17] compared these methods with the general-purpose ILP solvers CPLEX 4.0.8 and MINTO 2.3, observing that the latter ones have execution times competitive with that of the best exact algorithms for the SCP in the literature. In most industrial applications it is important to rely on heuristic methods in order to obtain \"good\" solutions quickly enough to meet the expectations of decision-makers. To this purpose, many heuristics have been presented in the literature. The classical greedy algorithm proposed by [PERSON] [18] sequentially inserts the set with a minimum _score_ in the solution. [PERSON] proved that the worst case performance ratio does not exceed \(H(d)=\sum_{i=1}^{d}\frac{1}{i}\), where \(d\) is the size of the largest set. More recently, [PERSON] [19] described a new approximation heuristics for the SCP. His algorithm involves the same scheme of [PERSON]'s procedure, but modifies the score by including a new parameter, named _difficulty_.