# Feasibility of linear inequalities with binary variables

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.

• I guess you mean 'binary' variable. This comes under the scope of integer linear programming, which is unfortunately an NP-Hard problem. – Abhishek Bansal Sep 11 '14 at 12:09
• Just to clarify on that: not only solving ILP for optimality is NP hard but also to find a feasible solution? – vkrouglov Sep 11 '14 at 17:13