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 ( \(\mathcal {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 \(\mathcal {NIA}\) benchmarks of SMT-LIB.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Boosting MCSat Modulo Nonlinear Integer Arithmetic via Local Search

  • Enrico Lipparini,
  • Thomas Hader,
  • Ahmed Irfan,
  • Stéphane Graham-Lengrand

摘要

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 ( \(\mathcal {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 \(\mathcal {NIA}\) benchmarks of SMT-LIB.