A Practical Approach to Satisfiability Modulo Linear Integer Arithmetic

Abstract

We present a detailed description of a theory solver for Linear Integer Arithmetic $\mathrm{(}\mathcal{LA}\mathrm{(}\mathbb{Z}\mathrm{)}\mathrm{)}$ in a lazy SMT context. Rather than focusing on a single technique that guarantees theoretical completeness, the solver makes extensive use of layering and heuristics for combining different techniques in order to achieve good performance in practice. The viability of our approach is demonstrated by an empirical evaluation on a wide range of benchmarks, showing significant performance improvements over current state-of-the-art solvers.