I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a feasible solution or prove that the system has no solutions? I need this to generate an initial solution to the heterogenuous fleet VRP where the number of unknowns is ~ 10s of millions in each instance.
Feasibility of linear inequalities with binary variables
algorithms;reference request;decision problem;integer programming
Use an off-the-shelf integer linear programming solver.  That's exactly what they are designed to do.  The problem is NP-hard in general, so there are no guarantees -- there are certainly some problems that no existing solver can solve in any reasonable amount of time -- but you might get lucky.Checking whether a feasible solution exists is also NP-complete, and it is (asymptotically, in general) about as hard as finding a feasible solution if one exists.