Boosting MCSat Modulo Nonlinear Integer Arithmetic via Local Search
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908655101673472 |
|---|---|
| author | Lipparini, Enrico Hader, Thomas Irfan, Ahmed Graham-Lengrand, Stéphane |
| author_facet | Lipparini, Enrico Hader, Thomas Irfan, Ahmed Graham-Lengrand, Stéphane |
| contents | The Model Constructing Satisfiability (MCSat) approach to the SMT problem extends the ideas of CDCL from the SAT level to the theory level. Like SAT, its search is driven by incrementally constructing a model by assigning concrete values to theory variables and performing theory-level reasoning to learn lemmas when conflicts arise. Therefore, the selection of values can significantly impact the search process and the solver's performance. In this work, we propose guiding the MCSat search by utilizing assignment values discovered through local search. First, we present a theory-agnostic framework to seamlessly integrate local search techniques within the MCSat framework. Then, we highlight how to use the framework to design a search procedure for (quantifier-free) Nonlinear Integer Arithmetic (NIA), utilizing accelerated hill-climbing and a new operation called feasible-sets jumping. We implement the proposed approach in the MCSat engine of the Yices2 solver, and empirically evaluate its performance over the N IA benchmarks of SMT-LIB. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Boosting MCSat Modulo Nonlinear Integer Arithmetic via Local Search Lipparini, Enrico Hader, Thomas Irfan, Ahmed Graham-Lengrand, Stéphane Logic in Computer Science The Model Constructing Satisfiability (MCSat) approach to the SMT problem extends the ideas of CDCL from the SAT level to the theory level. Like SAT, its search is driven by incrementally constructing a model by assigning concrete values to theory variables and performing theory-level reasoning to learn lemmas when conflicts arise. Therefore, the selection of values can significantly impact the search process and the solver's performance. In this work, we propose guiding the MCSat search by utilizing assignment values discovered through local search. First, we present a theory-agnostic framework to seamlessly integrate local search techniques within the MCSat framework. Then, we highlight how to use the framework to design a search procedure for (quantifier-free) Nonlinear Integer Arithmetic (NIA), utilizing accelerated hill-climbing and a new operation called feasible-sets jumping. We implement the proposed approach in the MCSat engine of the Yices2 solver, and empirically evaluate its performance over the N IA benchmarks of SMT-LIB. |
| title | Boosting MCSat Modulo Nonlinear Integer Arithmetic via Local Search |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2503.01627 |