Mixed Integer Linear Programming Verification

MILP (Mixed-Integer Linear Programming) Verification is the encoding of neural network verification problems as mixed-integer optimization problems — where ReLU activations are modeled as binary variables and the verification question becomes an optimization feasibility problem.

How MILP Verification Works

• Linear Layers: Encoded directly as linear constraints ($y = Wx + b$).
• ReLU: Modeled with binary variable $z \in {0, 1}$: $y \leq x - l(1-z)$, $y \geq x$, $y \leq uz$, $y \geq 0$.
• Objective: Maximize (or check feasibility of) the target property violation.
• Solver: Commercial solvers (Gurobi, CPLEX) solve the MILP with branch-and-bound.

Why It Matters

• Exact: MILP provides exact verification — no approximation, no false positives.
• Flexible: Can encode complex properties (multi-class robustness, output constraints).
• State-of-Art: Combined with bound tightening (CROWN bounds), MILP-based tools win verification competitions.

MILP Verification is optimization-based proof — encoding neural network properties as integer programs for exact formal verification.