Introduction
Modern combinatorial optimization solvers—used in fields ranging from scheduling to circuit design—rely on sophisticated "shortcuts" to navigate vast search spaces. Techniques like symmetry breaking and dominance breaking allow solvers to prune redundant branches, significantly boosting performance. However, these optimizations are notoriously difficult to implement correctly. A single bug can lead a solver to incorrectly claim a problem is unsatisfiable or miss an optimal solution.
This paper introduces a unified, machine-verifiable framework for certifying these complex moves. By extending pseudo-Boolean proof logging, the authors provide a robust method to ensure that solver "shortcuts" remain sound and complete.
A Unified Framework for Dominance
The core innovation of this work is the treatment of symmetry as a special case of dominance. The authors define a preorder ($\preceq$) where one solution dominates another if it is at least as good according to the objective function.
To certify these prunings, the authors introduce a new formal inference rule. When a solver adds a constraint to prune the search space, it must provide a witness—a mathematical mapping (substitution) demonstrating that any excluded solution can be transformed into a "better" or equivalent solution that remains in the search space. This approach turns a complex global property into a locally verifiable step.
Implementation and VeriPB
The framework is implemented as an extension to VeriPB, a tool for verifying pseudo-Boolean proofs using cutting planes reasoning. By using pseudo-Boolean constraints (0-1 linear inequalities) as a "lingua franca," the method bridges the gap between SAT solvers, Constraint Programming (CP), and Mixed-Integer Programming (MIP). The authors demonstrated the practicality of this approach by integrating proof logging into the high-performance SAT solver Kissat and the symmetry-breaking tool BreakID.
Empirical Evaluation
The authors evaluated the framework across 1,089 instances from SAT competitions (2016–2021), as well as CP benchmarks like the Crystal Maze puzzle and Maximum Clique problems.
Proof Logging Overhead
A critical requirement for any certification system is that it does not significantly hinder the solver's performance. The results show that the overhead for generating proofs is remarkably low. For 99% of the SAT instances tested, proof logging added less than 32% to the total solving time.
Verification Performance
While verification is inherently more computationally intensive than solving, the framework remains practical. The authors successfully verified symmetry breaking for 1,058 out of 1,089 instances. Notably, 75% of these instances were verified within 3.2x the original solving time.
Conclusion
This work provides the first unified method capable of certifying advanced SAT techniques alongside general symmetry and dominance breaking. While some challenges remain—such as high verification times in extreme cases and memory limitations for complex symmetries—the framework represents a major step toward "certified" combinatorial optimization. Future work aims to integrate these capabilities into mainstream CP and MIP solvers, expanding the reach of verifiable algorithmic reasoning.
Summary updated