Mar, 2022

解决布尔可满足性问题的机器学习方法

PDF
TL;DR本文综述了近期文献，重点介绍了利用机器学习技术来解决布尔可满足性问题（SAT）的方法，包括从基于手工特征的朴素分类器到最新的端到端 SAT 求解器 NeuroSAT，以及将现有的 CDCL 和本地搜索求解器与机器学习相结合的最新进展。总体而言，利用机器学习解决 SAT 是一个有前途但充满挑战的研究课题，文章指出了当前研究的局限性并提出了未来可能的方向。
boolean satisfiability problemmachine learning techniquessat solvershandcrafted heuristicsneurosat
发现论文，激发创造
  • SAT 问题的机器学习：约束启发式和新的图表示

    布尔可满足性 (SAT) 是一个基础的 NP-complete 问题，具有许多应用，包括自动计划和调度。为了解决大规模的情况，SAT 求解器必须依赖启发式算法，如在 DPLL 和 CDCL 求解器中选择一个分支变量。我们建议使用机器学习模型来改进这些启发式算法，通过减少步数来降低运行时间，但是由于有用的模型相对较大和较慢，这通常会阻碍运行时间。我们建议首先使用训练好的机器学习模型进行几个初始步骤，然后将控制权交给经典启发式算法，这简化了 SAT 求解的冷启动，并可以减少步数和总运行时间，但需要单独决定何时将控制权交给求解器。此外，我们介绍了一种改进的 Graph-Q-SAT，专门针对从其他领域转换而来的 SAT 问题，例如开放式车间调度问题。我们通过随机和工业 SAT 问题验证了我们方法的可行性。

    Jul, 2023

  • 利用深度学习构建带性能界限的随机局部搜索 SAT 求解器

    利用图神经网络训练适用于布尔可满足性问题的 SLS 求解器，可显著提高性能，平均解决比例更高、步骤更少，具有性能保证。

    Sep, 2023

  • 用概率方法扩展机器学习以解决组合优化问题的隐蔽博弈

    应用深度学习解决困难的组合问题具有巨大的潜力。该研究侧重于布尔可满足性（SAT）问题，并通过基本的概率方法消除了由于训练集仅限于小于实际问题规模几个数量级的随机公式导致的难题。使用我们的生成器，我们对现有的最先进模型进行训练，以预测具有 10,000 个变量的公式的可满足性，提出了新的分类器，可以对大多数困难水平的相同数据集进行显着改进，从而打破了过去基于公式的句法特征学习的方法，并使用求解器计算的简短前缀进行学习。

    Nov, 2022

  • NLocalSAT: 利用解预测提升局部搜索

    本文介绍了一种结合 solution prediction model 和神经网络的方法 ——NLocalSAT，用于提高 stochastic local search 在解 Boolean satisfiability problem 时的有效性，并且在 SAT Competition 2018 的实验中取得了 27% ~ 62% 的性能提升。

    Jan, 2020

  • 利用单位监督学习 SAT 求解器

    NeuroSAT 是一种信息传递神经网络，通过分类器训练来预测可满足性，在解决图着色、团检测、支配集和顶点覆盖等问题上具有较好的泛化性能。

    Feb, 2018

  • G2SAT：学习生成 SAT 公式

    本研究提出了 G2SAT 这一深度生成式框架，可以学习从输入公式集生成满足真实世界 SAT 实例特征的 SAT 公式，旨在扩展现有的数据集，为 SAT 求解器的性能提供优化方案。

    Oct, 2019

  • 解决四类 SAT 问题的通用方法

    该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT，用于解决不同类型的布尔可满足性问题，包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数，构建了统一的整数规划表示方法，并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构，在 SAT 问题上应用了蒙特卡罗树搜索（MCTS）方法，证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明，该方法能够剪枝不必要的搜索空间，找到问题的最优布尔赋值，同时为 SAT 问题的监督学习方法提供多样的标签。

    Dec, 2023

  • 通过机器学习解决混合整数规划问题的调查

    本文调查了利用机器学习解决混合整数规划（MIP）问题的趋势，介绍了 MIP 及其传统算法，提倡学习和 MIP 的不同集成，并引入了与学习相关的方法。最后，我们展望了基于学习的 MIP 求解器的前景。

    Mar, 2022

  • 学习选择 SAT 编码用于伪布尔和线性整数约束

    通过使用监督式机器学习方法，探讨选择伪布尔约束和线性约束的编码问题，我们展示了使用标准特征集和专门设计的特征集可以有效地选择编码，甚至对于未见过的问题类别也能取得良好的结果，相比使用相同特征集的 AutoFolio 结果有优势。我们讨论了实例特征对选择最佳编码任务的相对重要性，并比较了多种机器学习方法的变体。

    Jul, 2023

  • torchmSAT：一个 GPU 加速的最大可满足性问题的近似算法

    利用机器学习技术将离散结构与组合优化算法集成，提出一种能够近似求解最大满足性问题的可微函数，设计了一种新颖的神经网络结构并借助后向传播逐步求解问题，通过利用 GPU 进行计算加速，论文实验证明这种方法在挑战性的最大满足性问题上优于两种现有求解器，并与另一种求解器在解决成本方面相当，而无需进行训练或使用底层 SAT 求解器，为基于神经网络 GPU 加速的新一代求解器铺平了道路。

    Feb, 2024