Find exactly k columns in binary matrix such that the sum of those columns is the 1-vector

Question

Suppose I have an $M\times N$ binary matrix where $N$ can be large (say $N\approx10^6$). I want to find exactly $k$ columns ($k$ is relatively small, say $k<10$) such that the sum of those $k$ columns is the 1-vector (an $M$-dimensional vector with all components being 1). One solution is adequate.

For example, an algorithm working on the matrix $$\begin{pmatrix} 1 & 0 & 0\\ 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 1 & 1\\ \end{pmatrix}$$ should return columns 1 and 3 if $k=2$, but should report no solutions if $k=1$ or $k=3$.

I can get my computer to do an exhaustive check, but the best I've managed so far is worst-case $O(N^k)$ time complexity. I wonder whether there are any linear algebra, combinatorial or other techniques that can simplify the search? To be clear, the aim of this question is not necessarily about writing more efficient code, but rather if there are any maths tricks I can use to help simplify the problem. Thanks!

I've also asked this question on Stack Overflow where I'm more interested in help on improving algorithmic efficiency. The code I've used for exhaustive searching is there if you're interested.

Answer 1

This is a cardinality-constrained set partitioning problem. You can solve it via integer linear programming as follows. Let $a_{i,j}$ denote the matrix entry in row $i$ and column $j$. Let binary decision variable $x_j$ indicate whether column $j$ is selected. The constraints are: \begin{align} \sum_i a_{i,j} x_j&=1&&\text{for all $i$}\\ \sum_j x_j &=k \end{align}