I am trying to solve $Ax = b$ with the following properties:
- $A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$
- $A$ is of size $m \times n$ where $m \ll n$
- Each entry in $b$ is a non-negative integer
- Each entry in $x$ should be a non-negative integer
- It is known that such a $x$ exists
I am able to solve it as an integer linear program using standard LP solvers but how to solve it with a matrix based approach? Given the special properties of the problem, I believe there definitely would be some nice matrix based approach.
We may also relax $x$ to have non-negative real numbers and/or settle for an approximate solution if getting an exact solution in not easy.