TL;DR
This paper introduces a novel method for generating machine-checkable proofs for the "bounds propagation" step in constraint programming solvers, specifically for integer multiplication constraints. This allows for greater trust in solver results by providing verifiable justifications for how variable domains are narrowed, especially for complex arithmetic operations.
What Problem Does This Paper Address?
Constraint programming (CP) solvers are powerful tools for tackling complex problems by finding solutions or proving their non-existence. While verifying solutions is straightforward, trusting claims of unsatisfiability or optimality is harder due to the inherent complexity of solver software. Proof logging aims to address this by having solvers output a verifiable "certificate" alongside their results. Existing work has shown how to generate proofs for many standard CP constraints using pseudo-Boolean (PB) constraints (linear inequalities over 0-1 variables). However, justifying the inferences made by "bounds propagation" for non-linear constraints like multiplication (X * Y = Z) has remained a challenge, as it requires reasoning beyond simple linear inequalities. This paper tackles the problem of extending PB proof logging to effectively certify bounds propagation for integer multiplication.
Methods
The core of this paper is the development of a method to represent integer multiplication constraints and their bounds propagation within the pseudo-Boolean (PB) proof system.
- PB Encoding: The authors first represent CP variables with integer domains as sequences of PB bit variables. For positive domains, this is a standard binary representation. For domains including negative numbers, they employ a two's complement representation, carefully handling the sign bit.
- Magnitude Multiplication: They then establish PB encodings for the multiplication of the magnitudes of these variables. This involves defining auxiliary variables for bit-wise multiplications and then constraining the bits of the product variable (Z) based on the bits of the multiplicands (X and Y).
- Bounds Derivation: The key innovation lies in deriving bounds for the product variable (Z) based on the bounds of the multiplicands (X and Y) using PB proof rules. This is achieved through a series of logical steps involving:
- Cutting Planes Rules: Standard PB proof rules for manipulating linear inequalities.
- Saturation: A rule that strengthens inequalities by considering the minimum possible coefficient.
- Reverse Unit Propagation (RUP): A rule that allows deriving a constraint if its negation, combined with existing constraints, leads to a contradiction.
- Explicit Contradiction: Using proofs by contradiction to derive certain bounds.
- Case-Based Reasoning: Handling negative numbers and different sign combinations through explicit case analysis or by leveraging the properties of the PB encoding.
- Bounds on Multiplicands: The paper also shows how to justify bounds propagation for the multiplicands (X and Y) based on the bounds of the other variables (Y and Z, or X and Z), demonstrating symmetry.
- Comparison to Brute Force: The authors highlight that their method offers a significant advantage over a "brute force" approach of pre-computing all possible solutions and reifying them, in terms of both proof logging overhead and verification time.
Datasets
Not discussed in the paper. The experiments were conducted on "minimal CSP instances" and "synthetic instances" generated by the authors, as well as the "n-fractions" problem from CSPLib.
Key Insights and Ideas
- PB System's Expressiveness: The paper demonstrates that the seemingly limited linear PB proof system can effectively represent and justify non-linear reasoning like integer multiplication bounds propagation, by cleverly using binary representations and logical rules.
- Handling Negative Numbers: The approach for representing and reasoning about two's complement numbers within the PB framework is crucial for general-purpose multiplication constraints.
- Efficiency Gain: Specialized proof logging for bounds propagation is significantly more efficient than generic "auto-tabulation" methods, especially for larger domains or more complex constraints.
- Proof by Contradiction is Powerful: The paper effectively uses proofs by contradiction (RUP) to derive upper bounds and handle cases where direct derivation is complex.
- Symmetry in Bounds Propagation: The symmetry of the multiplication constraint allows the same techniques to be applied to derive bounds for any of the three variables (X, Y, or Z) given bounds on the other two.
Key Results
- The paper provides constructive proofs for deriving bounds on the product variable (Z) from bounds on the multiplicands (X and Y) using PB proof steps.
- It also shows how to derive bounds on multiplicands (X or Y) from bounds on the product and the other multiplicand.
- Empirical results (Figure 1) show that their proposed "BC Proof Logging" (Bounds-Consistent Proof Logging) is significantly faster than "Table Proof Logging" (auto-tabulation) in terms of both proof generation time and verification time. For instance, solve times for BC proof logging were orders of magnitude faster than table-based proofs.
- For the "n-fractions" problem, their method generated a 428MB proof in 8.8s, which was verified in 4864.5s. The table-based approach was stopped when the proof file exceeded 2TB.
Limitations and Future Work
- Implementation Dependency: The authors note that precise overheads can be highly implementation-dependent, as the solver continuously writes to disk.
- Future Work:
- A more comprehensive analysis of the solver's behavior on diverse benchmarks is needed.
- The paper suggests that the techniques developed (PB proofs with restrictions and proofs by contradiction) will be useful for implementing proofs for further constraints, especially those involving negative integer values.
- An open question remains whether an efficient pure cutting-planes derivation exists for certain types of constraints, as opposed to relying on RUP.
Summary updated