Suppose I have a linear system $$ A_{ij}X_j = B_i $$
where $A$ is a $m\times n$ of real values and $B$ is a vector of real values. When $X$ is allowed to be real, then a solution of this system for X exists if $A$ is invertible (which requires $A$ to be square and have at least the same dimension as $X$).
What if each element of the vector $X$ is only allowed to take the values 0 or 1? Is there a general procedure for solving for $X$? Can one make a general statement of how many linear equations are needed to find a solution?
This is an integer program, which is typically NP-hard. In some cases (when the integrality gap is zero), then we can relax the $x_j$ to be real valued, solve a linear program, and round the result to get the exact result. In general solving the LP-relaxation will not give you the correct solution.