Search papers, labs, and topics across Lattice.
This paper introduces LeanCSP, a framework designed for certifying both the reformulation of constraints and the correctness of solutions in constraint programming using the Lean theorem prover. By enabling the verification of formulation-level properties and the checking of solver-produced certificates, LeanCSP establishes a comprehensive workflow that ensures the reliability of constraint problem solutions without relying on external solvers. Experimental results demonstrate that verified symmetry breaking can significantly reduce solver search efforts, achieving reductions by factors as high as 20 million for certain problem families while maintaining efficient certification times.
Verified symmetry breaking in LeanCSP can reduce solver search efforts by up to 20 million times, revolutionizing trust in constraint programming results.
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.
