boolean satisfiability problem | BriefGPT

关键词boolean satisfiability problem

搜索结果 - 11

通过元启发式优化分解困难的 SAT 实例
在本文中，我们考虑了在布尔可满足性问题（SAT）的框架下，估计特定布尔公式的难度相对于特定完备 SAT 求解算法的问题。在我们引入了强背门集（SBS）概念之后，我们提出了分解难度（d-hardness）的概念，并通过使用蒙特卡罗方法等算法来
PDF7 months ago
新的布尔可满足性问题启发式策略：最小正负乘积策略
本研究提出了一种名为 “Minimal Positive Negative Product Strategy” 的新型启发式算法，用于指导 CDCL 算法解决布尔可满足性问题，它通过数学解释阐明了该算法相对于动态最大个体和变量状态独立衰减和
PDF8 months ago
G4SATBench：使用图神经网络对 SAT 求解进行基准测试和推进
通过建立一个全面的评估框架，我们提出了第一个用于 GNN-based SAT solvers 的基准研究，对各种预测任务、训练目标和推理算法的广泛范围的 GNN 模型进行了基准测试，结果展示了 GNN-based SAT solvers 的
PDF9 months ago
利用深度学习构建带性能界限的随机局部搜索 SAT 求解器
利用图神经网络训练适用于布尔可满足性问题的 SLS 求解器，可显著提高性能，平均解决比例更高、步骤更少，具有性能保证。
PDF10 months ago
学习选择 SAT 编码用于伪布尔和线性整数约束
通过使用监督式机器学习方法，探讨选择伪布尔约束和线性约束的编码问题，我们展示了使用标准特征集和专门设计的特征集可以有效地选择编码，甚至对于未见过的问题类别也能取得良好的结果，相比使用相同特征集的 AutoFolio 结果有优势。我们讨论了实
PDFa year ago
基于 GNN 的 SAT 求解中的变量依赖问题解决
AsymSAT 是一种基于 GNN 的架构，能够扩展 GNN-based 方法的解题能力，改善 SAT 问题求解的性能，并通过使用生成的相关预测来维护变量之间的依赖关系。
PDFa year ago
Denoising Diffusion for Sampling SAT Solutions
使用去噪扩散和图神经网络生成多样化的布尔可满足性问题的解决方案，结果比现有最佳纯神经方法的准确度相似，即使系统用标准求解器中的非随机解进行训练，生成的解决方案也极其丰富。
PDF2 years ago
基于树宽求解问题的高级工具和方法 - 扩展摘要
本文主要研究了基于逻辑的问题及基于 treewidth 的方法和工具，并提出了一种新类型的问题降解方法，其中问题为有界 treewidth 的量化布尔公式（QBF）。结果表明，treewidth 是设计现代求解器时应考虑的一项重要的测量标准
PDF2 years ago
解决布尔可满足性问题的机器学习方法
本文综述了近期文献，重点介绍了利用机器学习技术来解决布尔可满足性问题（SAT）的方法，包括从基于手工特征的朴素分类器到最新的端到端 SAT 求解器 NeuroSAT，以及将现有的 CDCL 和本地搜索求解器与机器学习相结合的最新进展。总体而
PDF2 years ago
IJCAINLocalSAT: 利用解预测提升局部搜索
本文介绍了一种结合 solution prediction model 和神经网络的方法 ——NLocalSAT，用于提高 stochastic local search 在解 Boolean satisfiability problem
PDF4 years ago
AAAIFourierSAT: 一个基于傅里叶展开的代数框架求解混合布尔约束问题
FourierSAT 是一种基于布尔函数的傅里叶分析的不完全的 SAT 求解器，其提出一种用于解决具有不同类型限制的系统的代数框架，并通过实验证明在某些基准测试上，它比其他解算器更具鲁棒性。
PDF5 years ago