Given a boolean matrix $M \in {\{ 0,1 \}}^{n \times m}$
A pseudo-rectangle of $M$ is defined as a pair of rows and columns of $M$. I.e. a pair $(I_n, I_m)$ such that $I_n \subseteq \{1,..,n\}, I_m \subseteq \{1,..,m\}$
Find the minimal set of pseudo-rectangles such that each $1$ cell in $M$ is covered by exactly 1 pseudo-rectangle and no pseudo-rectangle covers any $0$ cell
You can solve this as a set partitioning (also known as exact cover) problem as follows. For each pseudo-rectangle $R$ that does not contain a $0$ cell ($M_{i,j}=0$), let binary decision variable $x_R$ indicate whether $R$ is selected. The problem is to minimize $\sum_R x_R$ subject to $$\sum_{R: (i,j) \in R} x_R = 1 \quad \text{for all $(i,j)$ where $M_{i,j}=1$}$$