# A Surprisal-Based Greedy Heuristic for the Set Covering Problem
## 2 Surprisal-Based Greedy Heuristic
### The SBH Algorithm  
In this section, we describe the SBH greedy heuristic, that constitutes an improvement on the classic [PERSON] greedy procedure. As illustrated in Section 2.2, [PERSON]'s algorithm assigns each column \(j\) a score equal to the unit cost to cover the rows in \(I_{j}\). Then it iteratively inserts the columns with the lowest score in the solution set. However, this approach is flawed when rows in \(I_{j}\) are poorly covered. Indeed, it does not consider the probability that rows \(i\in I_{j}\) are covered by other columns \(j^{\prime}\in J_{i}\). Our algorithm aims to correct this by introducing an additional term expressing the \"surprisal\" that a column \(j\) is selected. Therefore, our score considers two aspects: the cost of a column \(j\) and the probability that the rows in \(I_{j}\) can be covered by other columns. To formally describe our procedure, we introduce some concepts from Information Theory. The term _information_ refers to any message which gives details in an uncertain problem and is closely related with the probability of occurrence of an uncertain event. Information is an additive and non-negative measure which is equal to 0 when the event is certain and it grows when its probability decreases. More specifically, given an event \(A\) with probability to occur \(p_{A}\), the _self-information_\(\mathcal{I}_{A}\) is defined as:  
\[\mathcal{I}_{A}=-\log(p_{A}). \tag{4}\]Self-information is also called _surprisal_ because it expresses the \"surprise\" of seeing event \(A\) as the outcome of an experiment. In the SBH algorithm, at each stage we compute the surprisal of each column. The columns containing row \(i\) are considered independent of each other, so the probability of selecting one of them (denoted as event \(\bar{A}\)) is  
\[p_{\bar{A}}=\frac{1}{|I_{i}|}. \tag{5}\]  
Therefore, the opposite event, i.e., selecting row \(i\) with a column different from the current one, is:  
\[p_{A}=1-\frac{1}{|I_{i}|}=\frac{|J_{i}|-1}{|J_{i}|}. \tag{6}\]  
The self-information measure contained in this event is:  
\[\mathcal{I}_{i}=-\log\biggl{(}\frac{|J_{i}|-1}{|J_{i}|}\biggr{)}. \tag{7}\]  
Thanks to the additivity of the self-information measure, surprisal of a column \(j\) can be written as:  
\[\mathcal{I}_{j}=\sum_{i\in I_{j}}\mathcal{I}_{i}=\sum_{i\in I_{j}}-\log \biggl{(}\frac{|I_{i}|-1}{|J_{i}|}\biggr{)}. \tag{8}\]  
We modify [PERSON]'s cost of column \(j\), i.e., \(\frac{c_{j}}{|I_{j}|}\), by introducing the surprisal of \(j\) to the denominator, in order to favor columns with high self-information. In particular, at each step we select the column that minimizes:  
\[\min_{j\in J}\frac{c_{j}}{|I_{j}|\cdot\mathcal{I}_{j}}, \tag{9}\]  
which is equivalent to  
\[\min_{j\in J}\frac{c_{j}}{|I_{j}|}\prod_{i\in I_{j}}\frac{|J_{i}|-1}{|I_{i}|}. \tag{10}\]  
This formulation is the same as minimizing the probability of the intersection of independent events, each of which selects a column, other than the current one, covering row \(i\). Two extreme cases can occur:  
* if column \(j\) is the only one covering a row \(i\in I_{j}\), it is no surprise that it is selected: in this case \(\mathcal{I}_{j}\) is high and the modified cost (9) of column \(j\) is 0 so that column \(j\) is included in the solution;
* if, on the other hand, all rows \(i\in I_{j}\) are covered by a high number of other columns \(j^{\prime}\in J_{i}\), surprisal \(\mathcal{I}_{j}\) is very low. In this case, the cost attributed to column \(j\) is greater than its [PERSON]'s cost. To illustrate this concept, we now present a numerical example. Let \[(a_{ij})=\left[ \begin{array}{cccc}1&1&0&0\\ 0&0&0&1\\ 1&1&1&0\\ 1&0&1&1\end{array} \right],\quad(c_{j})=[3\;1\;2\;5]\]  
be the coverage matrix and the column cost vector. We denote, with \(CH_{score}^{i}\) and \(SBH_{score}^{i}\), respectively, as the Chvatal and SBH scores vectors, at the \(i\)-th iteration.