Feasibility of linear inequalities with binary variables
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.