# A Surprisal-Based Greedy Heuristic for the Set Covering Problem
## 3 Experimental Results  
The aim of our computational experiments was to assess the performance of the SBH heuristic procedure with respect to the other greedy heuristics proposed in literature. We implemented the heuristics in C++ and performed our experiments on a stand-alone Linux machine with a 4 core processor clocked at 3 GHz and equipped with 16 GB of RAM. The algorithm was tested on 77 instances from [PERSON]'s OR Library [37]. Table 1 describes the main features of the test instances and, in particular, the column density, i.e., the percentage of ones in matrix \(a\) and column range, i.e., the minimum and maximum values of objective function coefficients. The remaining column headings are self-explanatory. Instances are divided into sets having sizes ranging from \(200\times 1000\) to \(1000\times\) 10,000. Set \(E\) contains small unicost instances of size \(50\times 500\). Sets 4, 5 and 6 were generated by [PERSON] and [PERSON] [12] and consist of small instances with low density, while sets \(A\) to \(E\) come from [PERSON] [13]. The remaining instances (sets \(NRE\) to \(NRH\)) are from [24]. Such instances are significantly larger and optimal solutions are not available. Similarly, Table 2 reports features of seven large scale real-word instances derived from the crew-scheduling problem [26]. We compared SBH with [PERSON]'s procedure [18] (CH) and the heuristic by [PERSON] [19] (KORD). Tables 3-5 report the computational results for each instance under the following headings:  
* Instance: the name of the instance where the string before \"dot\" refers to the set which the instance belongs to;
* BS: objective function value of the best known solution;* SOL: the objective function value of the best solution determined by the heuristic;
* TIME: the execution time in seconds;
* GAP: percentage gap between BS and the SOL value, i.e., \[\text{GAP}=100\times\frac{\text{SOL}-\text{BS}}{\text{BS}}\]  
Columns \"SBH vs. CH\" and \"SBH vs. KORD\" report the percentage improvement of SBH w.r.t. CH and KORD, respectively. Regarding Table 3, it is worth noting that our heuristic, compared to [PERSON]'s greedy procedure, had a smaller gap, ranging from 12.65% to 11.03%, with an average improvement of 1.42%. Among these instances, SBH provided a better solution than [18] in 19 out of 24 instance problems. We point out that the best objective function value was given by [PERSON]'s algorithm, which was slightly better than our SBH procedure (by only 0.59%), but was slower. Similar observations can be derived from Table 4. Here, SBH performed better, even though it differed from the [PERSON] algorithm by only 0.07%. Comparing SBH with CH, it is worth noting that only in 4 instances out of 45 did SBH obtain a worse solution. SBH came close to the optimal solution, with an average gap of 10.69%, and was better than CH by 2.62%. The execution time for all the instances averaged 0.113 s for CH, 0.230 s for the [PERSON] procedure and 0.564 s for SBH. Increasing the size of the instances (which is the case in _rail_ problems), [PERSON]'s algorithm became much slower. Consequently, on these instances we compared only the CH and SBH heuristics. On these instances, our SBH algorithm provided an average objective function improvement of 5.82% with comparable execution times. In conclusion, this first analysis showed that the new SBH heuristic generally produced very similar results with respect to [PERSON]'s heuristic. This is due to the fact that both heuristics consider the degree of row coverage, although in different ways, and, thus, the _difficulty_ in covering them. However, the large amount of time the KORD algorithm took to solve _rail_ instances points out that the use of SBH meets the requirements of real-time applications. Finally, the average percentage improvement