TL;DR
This paper introduces a novel approach to pseudo-Boolean (PB) solving by adapting conflict-driven clause learning (CDCL) techniques. By replacing the "saturation" rule with a "division" rule in conflict analysis, the authors achieve significantly faster solving times and more compact integer coefficients, leading to a competitive PB solver.
What Problem Does This Paper Address?
The paper tackles the challenge of efficiently solving Pseudo-Boolean (PB) constraints, which are linear inequalities over Boolean variables. While Conflict-Driven Clause Learning (CDCL) solvers have become highly effective for standard Boolean Satisfiability (SAT) problems, their underlying reasoning is considered weak. PB constraints offer a more expressive way to model problems in various domains, but harnessing their full potential for faster solving has been difficult. Existing PB solvers often struggle with performance, either by converting PB problems to SAT (losing expressiveness) or by using weaker reasoning methods that don't fully exploit the power of PB constraints. The core problem is bridging the gap between the theoretical strength of PB reasoning and practical, efficient solving.
Methods
The authors propose a modified conflict-driven pseudo-Boolean solving approach. The key innovation lies in their conflict analysis strategy. Instead of using the "saturation" rule (as in [Chai and Kuehlmann, 2005]), they introduce a "division" rule, inspired by the cutting planes method. This division rule allows for more powerful reasoning and, crucially, helps keep integer coefficients small during the search.
Their conflict analysis algorithm, "rounding," involves:
roundToOnefunction: This function takes a constraint, a literal, and a partial assignment. It weakens the constraint by removing literals not falsified by the assignment and whose coefficients are not divisible by the coefficient of the target literal. It then divides the constraint by this coefficient, resulting in a new constraint with a coefficient of 1 for the target literal. This process ensures the new constraint is a consequence of the original and maintains the crucial invariant that the derived constraint is falsified by the current trail.RoundingSatconflict analysis (Algorithm 6): This algorithm iteratively usesroundToOneto reduce both the conflict constraint and the reason constraint. It then performs generalized resolution. If overflow occurs, it rounds the constraint to a cardinality constraint. This process aims to learn stronger clauses that explain conflicts more effectively.
Datasets
The paper evaluates their solver, RoundingSat, on benchmarks from the Pseudo-Boolean Competitions (PBC) over the past two decades, specifically focusing on the DEC-SMALLINT-LIN category. They also use several families of crafted instances, including:
- Vertex cover, rectangular grids
- Subset cardinality, fixed bandwidth
- Subset cardinality, random matrices
- Perfect matching, random graphs
- Even colouring, odd-dimension grids
- Even colouring, random graphs
These benchmarks are chosen because they represent problems where pseudo-Boolean reasoning is expected to be crucial and where their solver was compared against other state-of-the-art PB and SAT solvers.
Key Insights and Ideas
- Division Rule is Key: Replacing the "saturation" rule with a "division" rule in conflict analysis is the central idea. This allows for stronger reasoning and, importantly, keeps integer coefficients manageable, enabling the use of fixed-precision arithmetic.
- Smaller Coefficients, Faster Arithmetic: The aggressive use of division leads to smaller integer coefficients, which significantly speeds up arithmetic operations within the solver.
- Stronger Conflict Analysis: The
roundToOnefunction and the overallRoundingSatconflict analysis algorithm generate more informative learnt clauses, which helps prune the search space more effectively. - Bridging the Gap: The approach effectively bridges the gap between the theoretical power of PB reasoning and the practical efficiency of CDCL solvers, achieving performance competitive with both.
- Simpler Implementation: The authors suggest their method is conceptually simpler to understand and implement compared to some other PB reduction techniques.
Key Results
- Competitive Performance: RoundingSat performs comparably to or better than other state-of-the-art PB solvers (Sat4j Res+CP, Open-WBO) on various benchmarks.
- Superior on PB-Crucial Instances: The solver excels on benchmarks where pseudo-Boolean reasoning is essential, such as pigeonhole principles and subset cardinality constraints, often solving them much faster than resolution-based solvers.
- Faster Search Speed: Table 3 shows that RoundingSat achieves a significantly higher number of conflicts per second compared to other PB solvers, often by one or several orders of magnitude.
- Efficient Handling of Coefficients: The division rule helps keep integer coefficients within 32-bit range for inputs with bounded coefficients, allowing for efficient fixed-precision arithmetic.
- Outperforms Saturation-based Methods: The paper suggests their division-based approach is superior to saturation-based methods for PB conflict analysis.
Limitations and Future Work
- Input Format Sensitivity: Like many PB solvers, RoundingSat is sensitive to the input format and performs poorly on CNF formulas.
- Future Work - CNF Conversion: A key future direction is to implement rules for rewriting CNF to more efficient linear constraints.
- Future Work - Lazy Cardinality Detection: The authors propose implementing lazy cardinality detection during proof search, which would only incur costs when there's a strong indication of its benefit.
- Future Work - Skipping Resolution: The paper mentions an idea of skipping resolution steps in conflict analysis when the slack is very negative, which could lead to more compact analyses but requires further empirical evaluation.
- Comparison to CutSat: While CutSat uses division, a direct empirical comparison of RoundingSat against CutSat on PB competition benchmarks was not performed.
Summary updated