QFLIA

QFLIA stands for Quantifier-Free Linear Integer Arithmetic. It is the quantifier-free fragment of arithmetic over integers, consisting of linear expressions and constraints where variables appear only linearly and no products of two variables are allowed. Formulas are built from integer variables using addition, subtraction, comparison operators, and constants, forming conjunctions of linear equalities and inequalities such as a·x + b·y ≤ c.

The satisfiability problem for QFLIA is decidable and, in general, NP-complete. This reflects the fact that, even though individual linear programs over the reals are solvable in polynomial time, enforcing integrality of variables makes the problem as hard as many classical combinatorial problems. Several structural cases have favorable behavior; for example, when the constraint matrix is totally unimodular, the linear programming relaxation yields integral solutions, avoiding explicit integer search.

In practice, QFLIA is a central theory in Satisfiability Modulo Theories (SMT). SMT solvers typically combine a solver for linear real arithmetic with integer reasoning, using techniques such as branch-and-bound, cutting planes (e.g., Gomory cuts), and other integer programming methods to enforce integrality. They may also exploit properties of specific problem instances, incremental solving, and interaction with other theories like uninterpreted functions.

Typical use cases include program verification, symbolic analysis, scheduling, resource allocation, and constraint-based reasoning where constraints are linear and variables are restricted to integers. Common examples involve constraints like 3x + 5y ≤ 20 with x and y integers. QFLIA therefore provides a powerful, well-studied fragment for automated reasoning about discrete systems.