实现高效的全解 SAT 求解器
本研究分析了现有的基于不可满足子公式识别的最大可满足性问题(MaxSAT)算法,并提出了几个关键性优化和新的替代算法,这些优化和新算法在实际应用中的 MaxSAT 实例上提供了显着的性能提升。
Dec, 2007
该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT,用于解决不同类型的布尔可满足性问题,包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数,构建了统一的整数规划表示方法,并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构,在 SAT 问题上应用了蒙特卡罗树搜索(MCTS)方法,证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明,该方法能够剪枝不必要的搜索空间,找到问题的最优布尔赋值,同时为 SAT 问题的监督学习方法提供多样的标签。
Dec, 2023
FourierSAT 是一种基于布尔函数的傅里叶分析的不完全的 SAT 求解器,其提出一种用于解决具有不同类型限制的系统的代数框架,并通过实验证明在某些基准测试上,它比其他解算器更具鲁棒性。
Dec, 2019
AutoSAT 是一种自动优化 SAT 解算器中启发式算法的新框架,基于大型模型(LLMs),它能够自主生成代码、进行评估,并利用反馈进一步优化启发式算法,从而减少人工干预并增强解算器的能力。AutoSAT 在插拔式基础上操作,不需要广泛的预备设置和模型训练,促进了具有容错性的思维链的合作过程,确保了强大的启发式优化。对 Conflict-Driven Clause Learning (CDCL) 解算器进行的大量实验证明了 AutoSAT 的整体优异性能,特别是在解决一些特定的 SAT 问题实例中。
Feb, 2024
本研究提出了 G2SAT 这一深度生成式框架,可以学习从输入公式集生成满足真实世界 SAT 实例特征的 SAT 公式,旨在扩展现有的数据集,为 SAT 求解器的性能提供优化方案。
Oct, 2019
本文提出了一种使用中国剩余定理将整数因子分解问题转化为 SAT 问题的算法,能够生成与 100 位整数因子分解一样难度的约 5600 变量的 SAT 实例。
Sep, 1998
提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题,并基于此方法设计了两个实用算法:一个近似均匀生成器和一个可扩展的近似模型计数器,该方法具有强大的理论保证和可扩展性,可适用于不同的应用领域。
Apr, 2014
本文综述了近期文献,重点介绍了利用机器学习技术来解决布尔可满足性问题(SAT)的方法,包括从基于手工特征的朴素分类器到最新的端到端 SAT 求解器 NeuroSAT,以及将现有的 CDCL 和本地搜索求解器与机器学习相结合的最新进展。总体而言,利用机器学习解决 SAT 是一个有前途但充满挑战的研究课题,文章指出了当前研究的局限性并提出了未来可能的方向。
Mar, 2022
本文介绍了使用因果推理探究 SAT 求解器内在工作机制的方法 CausalSAT,并通过实验验证了其中四条经验法则和三个与现代 SAT 求解器实现密切相关的问题。
Jun, 2023