Towards Modern and Modular SAT for LCG (Short Paper)

Jip J. Dekker, Alexey Ignatiev, Peter J. Stuckey, Allen Z. ZhongCP 2025 · OpenReview

TL;DR

This paper introduces "Huub," a novel Lazy Clause Generation (LCG) solver that leverages the IPASIR-UP interface to seamlessly integrate modern, high-performance SAT solvers. By decoupling the CP and SAT components, Huub demonstrates that modern SAT technology can significantly boost LCG solver performance, paving the way for more competitive constraint programming solutions.

What Problem Does This Paper Address?

Constraint Programming (CP) solvers often rely on Boolean Satisfiability (SAT) engines for their reasoning and search capabilities. Lazy Clause Generation (LCG) is a popular architecture that bridges CP and SAT, where CP propagators lazily generate clauses that the SAT engine uses to find solutions. However, a significant gap exists: while SAT solvers have seen rapid advancements in recent years (e.g., inprocessing, improved search strategies), many LCG solvers still use older SAT technology. This limits their potential. The paper addresses this by exploring how to effectively integrate modern SAT solvers into the LCG framework, specifically through the IPASIR-UP interface, and re-evaluating LCG design decisions in light of these advancements.

Methods

The core contribution is the development of Huub, an LCG solver built using the IPASIR-UP interface. This interface acts as a bridge, allowing a SAT solver to interact with an external propagation engine (the LCG backend).

Key methodological aspects include:

  • Modular SAT Integration: Instead of tightly coupling a custom SAT solver, Huub uses IPASIR-UP to allow swapping out different SAT solvers, benefiting from their latest features.
  • Revisiting LCG Design: The paper re-examines fundamental LCG design choices, such as explanation mechanisms (forward vs. backward, clausal vs. hybrid) and adaptive propagation, to best leverage modern SAT capabilities.
  • Hybrid Explanation: A novel hybrid approach to explanation is proposed, combining clausal and backward explanation with a threshold parameter to balance performance and overhead.
  • Adaptive Propagation: An adaptive scoring mechanism is introduced to conditionally disable propagators based on their activity, aiming to improve efficiency.

Datasets

The paper evaluates Huub on benchmarks from the MiniZinc Challenge 2024. These benchmarks consist of 20 problems with 5 instances each, covering a range of constraint satisfaction problems. The authors note that Huub's propagators support all FlatZinc primitive constraints and the all_different and disjunctive global constraints, with others being decomposed.

Key Insights and Ideas

  • Modern SAT Solvers are a Game Changer for LCG: The most significant insight is that by simply leveraging modern SAT solvers through an interface like IPASIR-UP, LCG solvers can achieve competitive performance without needing to reinvent the SAT engine itself.
  • Modularity is Key: The IPASIR-UP interface enables a modular approach, allowing LCG solvers to benefit from ongoing SAT solver improvements without requiring fundamental changes to the LCG architecture.
  • Explanation Strategies Matter: The way CP propagations are explained to the SAT solver has a direct impact on performance. A hybrid approach, carefully balancing clausal and backward explanation, can yield better results than purely one or the other.
  • Adaptive Propagation Offers Nuance: While adaptive propagation can improve performance by disabling less useful propagators, its effectiveness depends on the specific problem and the chosen mechanism. Fine-grained adaptive strategies are more promising than a blanket approach.

Key Results

  • Competitive Performance: Huub, using the IPASIR-UP interface and a modern SAT solver (CaDiCaL), demonstrates competitive performance against state-of-the-art LCG solvers like Chuffed and CP-SAT on the MiniZinc Challenge 2024 benchmarks.
  • SAT-Based Search Advantage: Huub performs best when utilizing the SAT solver's search heuristic ("SAT-based search") rather than a fixed search strategy.
  • Hybrid Explanation Benefits: Increasing the number of clauses pushed to the SAT solver via a hybrid explanation strategy (with an optimal threshold) led to a higher number of optimally solved instances. For instance, a threshold of L=5 improved performance.
  • Inprocessing Boosts Performance: Enabling various inprocessing techniques in the SAT solver provided a slight but consistent improvement in solver performance.
  • Adaptive Propagation Nuances: While directly applying an adaptive engine reduced optimality, adaptive propagators with an appropriate threshold slightly improved performance on specific problem categories.

Limitations and Future Work

  • Limited Global Constraint Support: Huub currently implements propagators for only a subset of global constraints (all_different, disjunctive). The authors acknowledge that performance could be significantly improved with more efficient propagators for other global constraints.
  • Further Investigation of Adaptive Propagation: The paper suggests that adaptive propagation, while promising, requires further investigation and refinement.
  • Dynamic Constraint Decomposition: The authors plan to explore other options in the future, such as dynamically decomposing constraints and encoding them into the SAT solver on the fly.
  • Exploring Other SAT Solvers: The IPASIR-UP interface allows for swapping SAT solvers, and future work could explore the impact of different modern SAT solvers on Huub's performance.

Summary updated

Abstract

Lazy Clause Generation (LCG) is an architecture for building Constraint Programming (CP) solvers using an underlying Boolean Satisfiability (SAT) engine. The CP propagation engine lazily creates clauses that define the integer variables and impose problem restrictions. The SAT engine uses the clausal model to reason and search, including, crucially, the generation of nogoods. However, while SAT solving has made significant advances recently, the underlying SAT technology in most LCG solvers has largely remained the same. Using a new interface to SAT engines, IPASIR-UP, we can construct an LCG solver which can swap out the underlying SAT engine with any that supports the interface. This new approach means we need to revisit many of the design and engineering decisions for LCG solvers, to take maximum advantage of a better underlying SAT engine while adhering to the restrictions of the interface. In this paper, we explore the possibilities and challenges of using IPASIR-UP for LCG, showing that it can be used to create a highly competitive solver.
BibTeX
@inproceedings{dekker2025towards,
  author = {Jip J. Dekker and Alexey Ignatiev and Peter J. Stuckey and Allen Z. Zhong},
  title = {{Towards Modern and Modular SAT for LCG (Short Paper)}},
  booktitle = {CP},
  year = {2025},
  url = {https://openreview.net/forum?id=15lOb7Tymy},
}
Figure