arXiv:2606.06656cs.AIcs.LO2026-06

将布尔满足性问题转为连续优化,提升求解效率。

A Study of Parallel Continuous Local Search

论文配图:A Study of Parallel Continuous Local Search
图 1 · 摘自论文原文
  • 将PB约束的布尔满足问题转化为超立方体上的连续优化
  • 冗余约束会阻碍收敛,局部搜索快速达到稳定解质量分布
  • 适合在混合求解框架中作为子求解器,适用于现代加速硬件

我们研究并行连续局部搜索(CLS)作为具有对称伪布尔(PB)约束的布尔满足性问题的求解方法。将n变量的PB可满足性问题松弛为n维超立方体上的可微目标函数的连续优化问题。对于可满足实例,该优化问题的全局极小值点对应于原SAT问题的满足赋值。通过实验发现:(i) 冗余约束反而抑制而非加速收敛;(ii) CLS在混合设置中表现出色,能快速完成部分赋值;(iii) 由于鞍点密集的目标函数,局部搜索迅速收敛至稳定的解质量分布(即满足度),后续迭代收益递减。这些发现为在现代加速器硬件上使用CLS求解SAT提供了实践指导。

原文摘要 · Abstract (English)

We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints. Here, the $n$-variable PB-satisfiability problem is relaxed to a continuous optimisation problem with a differentiable objective function on an $n$-dimensional hypercube. For satisfiable instances, the global minimisers of this optimisation problem correspond to satisfying assignments of the SAT problem at hand. We present several novel findings via empirical experiments: (i) redundant constraints can inhibit rather than accelerate convergence; (ii) CLS shows promise as a sub-solver in hybridised settings, quickly completing partial assignments; and (iii) local search rapidly converges to a stable distribution of solution quality (i.e., degree of satisfaction), due to saddle-dense objectives where additional solver steps yield diminishing returns. Our findings inform practical uses of CLS for SAT on modern accelerator hardware.

连续优化布尔满足局部搜索加速器

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。