Suppose we forget about optimizing and just want to find a feasible solution to a set of equations:$$\sum_i w_{ij} x_i = W_j.$$Here we are given $w_{ij}$ and $W_j$, and want to solve for $x_i$.  Also $x_i$ are restricted to be 0/1 and we're promised that $w_{ij}$ and $W_j$ will be non-negative integer constants and we will have $w_{ij} \leq M$ for some universal constant $M$.  The number of variables and equations can be arbitrary.Is this an NP-complete problem? If we have just one or a universal bounded number of equations then the problem can be solved in polynomial time. Certainly if we can find a solution then we can verify it in polynomial time, so the problem is in NP. I was trying to find a reduction from something like 3-SAT in the general case but to no avail.
Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard?
complexity theory;np complete
This problem is NP-complete, by reduction from 1-in-3 positive 3SAT.1-in-3 positive 3SAT is a variant of 3SAT, where we require that exactly each clause consists of 3 positive literals (no negation), and to satisfy the formula, exactly one literal in each clause must be true (no more, no less).  Thus, each 1-in-3 positive 3SAT instance is a formula$$\varphi(x_1,\dots,x_n) = \bigwedge_i (x_{c_{i,1}} \sqcup x_{c_{i,2}} \sqcup x_{c_{i,3}}),$$where $x \sqcup y \sqcup z$ is true iff exactly one of $x,y,z$ is true.You can immediately convert this to an instance of your problem.  In particular, the $i$th clause corresponds to an equation$$x_{c_{i,1}} + x_{c_{i,2}} + x_{c_{i,3}} = 1.$$For instance, the clause $(x_3 \sqcup x_5 \sqcup x_6)$ corresponds to the equation $x_3 + x_5 + x_6 = 1$.We get one equation per clause.  The equations are simultaneously satisfiable iff the formula $\varphi$ is satisfiable.  This completes the reduction.