arXiv:2507.00557v3 cs.AI

하이브리드 SMT-NRA 풀이기: 2차원 셀 점프 기반 지역 탐색, MCSAT, OpenCAD의 통합

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

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

제출 2026-11-02

한국어 초록

본 논문에서는 비선형 실수 산술 이론에 대한 만족 가능성 판정(SMT-NRA)을 위한 하이브리드 프레임워크를 제안한다. 먼저 SMT-NRA 지역 탐색 방법의 핵심 연산인 셀 점프(cell-jump)를 일반화한 2차원 셀 점프 이동인 \emph{2D-cell-jump}를 도입한다. 주어진 직선을 따라서만 할당을 갱신하는 기존의 셀 점프와 달리, 2D-cell-jump는 임의로 선택한 평면 위에서의 탐색을 가능하게 한다. 이어서 (SMT-NRA를 위한 기존 지역 탐색 프레임워크 LS를 따라) \emph{2D-LS}라 명명한 확장 지역 탐색 프레임워크를 제안한다. 마지막으로 정보 교환을 통해 탐색 효율을 높이기 위해 2D-LS, MCSAT, OpenCAD를 통합한 SMT-NRA용 하이브리드 프레임워크를 제시한다. 실험 결과는 지역 탐색 성능의 향상을 보여주며, 제안한 방법의 효과를 부각한다.

원문 초록

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 \emph{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 \emph{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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2507.00557v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.