Solving $Ax = b$ for non-negative $x$ given boolean matrix $A$ and non-negative $b$

Question

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.

Answer 1

This sounds similar to the Min/Max Flow problem and using the Network Simplex Method to solve the integer model of the following form:

$$\min z = \sum_{(i,j)\in E}c_{(i,j)}x_{(i,j)}$$ $$\text{Subject to:}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$$ $$\sum_{(i,j)\in E} x_{(i,j)} -\sum_{(i,j)\in E}x_{(i,j)}=b_m\quad\forall m\in{1, 2,\ldots,m}$$ $$0\le x_{(i,j)} \le u_{(i,j)}\quad\forall (i,j)\in E$$ $$x_{(i,j)}\in\mathbb{Z}^+\quad\forall (i,j)\in E$$

where $E$ denotes the set of all arcs in a graph, $x_{(i,j)}$ is the decision variable denoting the number of resources go from which node to another via arc $(i,j)$, and $u_{(i,j)}$ is the upper bounds of each decision variable. Given the notion that the entire coefficient matrix of $A$ is binary (there exists a connection from one node to another), and that arcs can only have non-negative, integer flows, then solving the mentioned problem via the Network Simplex method could be done via a matrix approach that takes advantage of the behaviors and sparcities of the constraint matrix since it heavily relies on all the properties you've mentioned.

However, since it's a rather large algorithm in terms of background (substantially more than this thread), here are some resources for better understanding how to use it in both its matrix form and graphically.