We propose a novel, sound, and complete Simplex-based algorithm for solving linear inequalities over integers. Our algorithm, which can be viewed as a semantic generalization of the
technique, systematically discovers and excludes entire subspaces of the solution space containing no integer points. Our main insight is that by focusing on the
of a vertex, we can compute a
proof of unsatisfiability
for the intersection of the defining constraints and use this proof to systematically exclude subspaces of the feasible region with no integer points. We show experimentally that our technique significantly outperforms the top four competitors in the QF-LIA category of the SMT-COMP ’08 when solving linear inequalities over integers.