Efficiently Computing a Non-negative Solution for an Underdetermined System of Linear Equations with 0-1 Coefficient Matrix

Question

I have a system of linear diophantine equations having $m$ constraints and $n$ variables, where $n>>m$. The coefficient matrix has all entries either 0 or 1. I am interested in finding a non-negative solution to this system very efficiently. An approximate solution that satisfies the constraints with bounded error will also do. Any pointers to this problem would be really helpful.

Answer 1

Suppose the linear system is $Ax=b$. You can solve the problem via mixed integer linear programming, as follows. For each constraint $i$, introduce nonnegative surplus and slack variables $s_i$ and $t_i$, respectively. The problem is to minimize $\sum_i (s_i+t_i)$ subject to \begin{align} Ax-s+t&=b \\ x &\ge 0 \text{ integer}\\ s &\ge 0\\ t &\ge 0 \end{align} As usual with mixed integer linear programming, the linear programming relaxation provides a lower bound. This formulation does not depend on the entries $A$ being 0-1.