Skip to content
Conference Open access

Towards Cardinality-Aware Local Search for SAT with Cardinality Constraints

Sep 2026 · Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence · 0 citations · 43 references

TL;DR

A cardinality-aware local search framework to solve SAT with cardinality constraints, denoted as CardSAT-LS, which integrates a preprocessing phase based on the generalized unit propagation and resolution, a cardinality-sensitive scoring function combining the make-break mechanism and cardinality violation, and an initialization based on fake-backbone variables.

Abstract

Satisfiability (SAT) with cardinality constraints arises naturally in many practical applications, where high-level counting requirements coexist with standard Conjunctive Normal Form (CNF) clauses. Translating these constraints into CNF can destroy structural information, limiting the effectiveness of search-based heuristics. In this paper, we propose a cardinality-aware local search framework to solve this problem, denoted as CardSAT-LS. CardSAT-LS integrates a preprocessing phase based on the generalized unit propagation and resolution, a cardinality-sensitive scoring function combining the make-break mechanism and cardinality violation, and an initialization based on fake-backbone variables. Furthermore, CardSAT-LS employs a unified framework that adaptively alternates between flip and swap operators when the search gets trapped in local optima. Finally, we conduct experiments on five public benchmarks from real-world applications as well as the MaxSAT and SAT competitions. Compared with ten state-of-the-art competitors, including SAT, MaxSAT, and PB solvers, CardSAT-LS solves the most instances with the lowest PAR-2 score. Additionally, we integrate CardSAT-LS into exact solvers for phase selection, which leads to significant speedups.

Read PDF

Similar papers

Conference Open access Sep 2026

Weight-Aware Branch-and-Bound for Weighted Maximum Satisfiability

The Weighted Partial MaxSAT (WPMS) problem requires finding an assignment that satisfies all hard clauses while maximizing the total weight of satisfied soft clauses. From a computational perspective, WPMS is not merely an extension of the uniform-weight Partial MaxSAT (PMS); rather, it requires search strategies that...

Jialu Zhang, Chumin Li, Sami Cherif et al. · 0 citations
Conference Open access Sep 2026

ULE-MWC: An UnLocking-Enhanced Lookahead Framework for Exact Maximum Weight Clique Search

A new solver is developed, ULE-MWC (UnLocking Enhanced MWC), which consistently yields tighter upper bounds and outperforms state-of-the-art exact solvers in both runtime and search efficiency.

Mingming Jin, Chu-Min Li, Kun He · 0 citations
Open access Oct 2026

Semi-declarative Language for Combinatorial Search

This work proposes SetLah!, a semi-declarative language for combinatorial search that addresses the shortcomings of both SAT and ASP, and built a compiler from SetLah! programs into ASP, allowing it to take full advantage of the existing efficient ASP solvers, while also automatically optimising the generated encodings...

Zi-Yi Yang, Ilya Sergey · 0 citations
Open access Sep 2026

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving

A resolvable network is a directed-graph representation of SAT: every SAT instance can be translated into an RN, and every RN has an associated CNF formula. Each reach represents one clause. In a mixed reach, the head and tail are disjoint sets of variables containing the variables occurring negatively and positively i...

Gábor Kusper · 0 citations
Preprint Oct 2026

Cores Characterize the One-Pass Streaming Complexity of CSPs

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly...

Joshua Brakensiek, Aaron L. Putterman, Amatya Sharma et al. · 0 citations

Test-Time Scaling via Budgeted Multi-Attribute Verification

Verifying LLM-generated answers under a shared computational budget requires jointly deciding which candidates to inspect and which verification attributes to evaluate. We formulate this problem as multi-attribute good-arm identification under a global budget: each candidate is an arm evaluated along several costly att...

Bo Xue, Ji Cheng, Shenghao Lyu et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.