# Elegant way to obtain the smallest subset of binary matrix rows where each column sums to at least 1

Context: I have $$m$$ groups of a random number of $$n$$ types. Each type can occur only once for each group. I hope to reduce the groups to the smallest set such that each type occurs at least once.

Problem: Suppose I have an $$n * m$$ binary matrix which represents the groups of each type.

$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{matrix}$$

Question: Is there an elegant way to determine the smallest subset of rows such that each column sums to at least $$1$$.

In this example rows 1, 3 and 4 fulfill this.

$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{matrix}$$

I am a biological scientist, so it may be obvious that this is not possible. My Google and Stack Exchange searches did not reveal a method.

This is a set covering problem, which you can solve via integer linear programming as follows. Let $$a_{i,j}$$ be the $$(i,j)$$ entry of your matrix. Let binary decision variable $$x_i$$ indicate whether you select row $$i$$. The problem is to minimize $$\sum_{i=1}^n x_i$$ subject to linear constraints: $$\sum_{i=1}^n a_{i,j} x_i \ge 1$$ for each $$j\in\{1,\dots,m\}$$.