并行连续局部搜索的研究

arXiv:2606.06656v1 公告类型：新 摘要：我们研究并行连续局部搜索（CLS）作为具有对称伪布尔（PB）约束的布尔可满足性问题的解决方法。在这里，$n$ 变量的 PB 可满足性问题被放松为在 $n$ 维超立方体上具有可微目标函数的连续优化问题。对于可满足的实例，该优化问题的全局极小值对应于当前 SAT 问题的满足分配。我们通过实证实验提出了一些新颖的发现：（i）冗余约束可以抑制而不是加速收敛； (ii) CLS 在混合设置中显示出作为子求解器的前景，可以快速完成部分任务； (iii) 由于鞍密集目标，额外的求解器步骤会产生收益递减，局部搜索迅速收敛到解质量的稳定分布（即满意度）。我们的研究结果为 SAT 在现代加速器硬件上的 CLS 实际应用提供了信息。