cs.AIJul 1, 2025

A Hybrid SMT-NRA Solver: Integrating 2D Cell-Jump-Based Local Search, MCSAT and OpenCAD

Authors: Tianyi Ding, Haokun Li, Xinpeng Ni, Bican Xia, Tianqi Zhao

Organizations: Peking University, China · Zhongguancun Laboratory, China

Abstract

In this paper, we propose a hybrid framework for Satisfiability Modulo the Theory of Nonlinear Real Arithmetic (SMT-NRA for short). First, we introduce a two-dimensional cell-jump move, called 2D-cell-jump, generalizing the key operation, cell-jump, of the local search method for SMT-NRA. In contrast to the existing cell-jump, which updates assignments exclusively along a given line, the 2D-cell-jump enables search over an arbitrarily selected plane. Then, we propose an extended local search framework, named 2D-LS (following the existing local search framework, LS, for SMT-NRA). Finally, we present a hybrid framework for SMT-NRA integrating 2D-LS, MCSAT and OpenCAD, to improve search efficiency through information exchange. The experimental results demonstrate improvements in local search performance, highlighting the effectiveness of the proposed methods.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Continuous Optimization for Satisfiability Modulo Theories on Linear Real Arithmetic

    Mar 24, 2026Yunuo Cen, Daniel Ebler, Xuanyao FongSatisfiability Modulo Theories

  2. Using GPUs And LLMs Can Be Satisfying for Nonlinear Real Arithmetic Problems

    Mar 8, 2026Christopher Brix, Julia Walczak, Nils Lommen +1Satisfiability Modulo Theories

  3. A Study of Parallel Continuous Local Search

    Jun 4, 2026Cody J Christopher, Charles GrettonMetaheuristic OptimizationCombinatorial Optimization