A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.

Most linear programming solvers check for feasibility first (usually this takes as much time as the second phase, which is actually finding the optimum, and uses the exact same algorithm). I would advise reading a standard textbook on the subject (Luenberger is good, Schrijver great if you are interested in integer/mixed problems). 


You haven't said whether you're interested in theoretical analysis or practical computation. At the practical level, you also haven't specified whether you can live with an approximate floating point solution or whether you need a solution that is exactly feasible (e.g. a solution expressed in infinite precision rational numbers.) Finally, if you are interested in doing this in practice, it would be important to know something about the size of the problem instances that you need to solve. From the point of view of practical computation with floating point numbers on problems of reasonable size (problems with hundreds of thousands of constraints and millions of variables are often solved in practice), using a good LP solver is definitely the way to proceed this technology has been developed to a very high level and nothing you could cook up would be faster. From the theoretical point of view, the LP formulation is solvable in polynomial time. I don't believe that you can get any improvement in the computational complexity by solving a feasibility problem rather than the optimization version of the problem. 

