← All papers
First page of LeanCSP: A Framework for Certifying Constraint Reformulation and Solving in Lean

LeanCSP: A Framework for Certifying Constraint Reformulation and Solving in Lean

Pablo Manrique, Stefan Szeider

cs.AI Jul 30, 2026 · v1 cs.LO
LeanCSP formalizes constraint satisfaction problems in Lean, proving reformulation soundness and checking external solver certificates back inside Lean.
Constraint programming is a core technology for solving complex combinatorial problems in scheduling, planning, configuration, and verification. Trusting its results therefore demands guarantees at two levels: that reformulations applied beforehand are semantics-preserving, and that solvers produce correct answers. In this work, we introduce a framework that addresses both verification levels in the Lean theorem prover: it can be used to prove formulation-level properties, such as equivalence, equisatisfiability, and the correctness of symmetry-breaking constraints, parametrically for entire problem families; and to check solver-produced certificates for individual instances via translation backends to external formats such as MiniZinc, SMT-LIB, and OPB. Combining both levels yields an end-to-end workflow that establishes the satisfiability or unsatisfiability of a constraint problem without trusting the external solver. Experimental results show that our framework's verified symmetry breaking also pays off in practice: a single parametric proof per problem family, reused across all instance sizes, reduces solver search effort by a factor of up to 2x10^7, while the entire in-Lean certification stays affordable, taking at most a few minutes for our largest instances.

Trusting constraint programming results requires guarantees that reformulations (e.g., symmetry-breaking) are semantics-preserving and that solver answers are correct. Errors in reformulations can silently flip satisfiability, and solvers themselves may contain bugs.

CSPs are formalized in Lean using dependent types, with reformulation properties (equivalence, equisatisfiability, symmetry-breaking soundness) provable parametrically for entire problem families. Instances are translated to external formats (MiniZinc, SMT-LIB, OPB), and solver certificates are re-imported and checked in Lean via decide (SAT) or PBLean checking VeriPB proofs (UNSAT). A verified CSP-to-pseudo-Boolean translation grounds the unsatisfiability path, keeping external solvers outside the trusted base.

Verified symmetry-breaking reduces solver search effort by up to 2x10^7, with a single parametric proof reused across instance sizes. End-to-end in-Lean certification stays affordable, at most a few minutes for the largest instances.

Familyw/o SBC (det)w/ SBC (det)Speedup (det)
Clique1.1e105.5e219,863,281
Myciel.4.4e91.4e7303
Schurt/o1.0e9
Odd cyc.4.6e25.2e18.8
vdW4.3e63.0e61.4
Effect of verified symmetry-breaking constraint (SBC) per family: deterministic step counts and speedup