随机 3-SAT 问题的搜索与启发式算法的共生
布尔可满足性 (SAT) 是一个基础的 NP-complete 问题，具有许多应用，包括自动计划和调度。为了解决大规模的情况，SAT 求解器必须依赖启发式算法，如在 DPLL 和 CDCL 求解器中选择一个分支变量。我们建议使用机器学习模型来改进这些启发式算法，通过减少步数来降低运行时间，但是由于有用的模型相对较大和较慢，这通常会阻碍运行时间。我们建议首先使用训练好的机器学习模型进行几个初始步骤，然后将控制权交给经典启发式算法，这简化了 SAT 求解的冷启动，并可以减少步数和总运行时间，但需要单独决定何时将控制权交给求解器。此外，我们介绍了一种改进的 Graph-Q-SAT，专门针对从其他领域转换而来的 SAT 问题，例如开放式车间调度问题。我们通过随机和工业 SAT 问题验证了我们方法的可行性。
Jul, 2023
这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题，介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中，在计算代价随问题规模呈指数级增长的情况下，首次发现了 “随机一阶相变” 的本质，并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。
Oct, 1999
提出一种基于连续局部搜索与信念传播结合的算法 GradSAT，能在求解混合布尔约束问题方面有很好的应用表现，对称布尔约束和小系数伪布尔约束也可适用，并有望成为解决布尔满足性和优化问题的有效方法之一。
Dec, 2020
介绍了 AlphaMapleSAT，一种新颖的基于蒙特卡罗树搜索 (MCTS) 的 Cube-and-Conquer (CnC) SAT 求解方法，旨在高效地解决具有挑战性的组合问题。
Jan, 2024
本文提出了一种选择最适合子问题的启发式算法的方法，并实验验证在各种 MIP 示例中，该方法相较于传统的使用单一启发式算法的算法选择方法，在目标值上表现更优。
Jul, 2013
提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题，并基于此方法设计了两个实用算法：一个近似均匀生成器和一个可扩展的近似模型计数器，该方法具有强大的理论保证和可扩展性，可适用于不同的应用领域。
Apr, 2014
我们对神经网络与组合优化中的局部搜索算法进行了综合研究，结果表明基于禁忌搜索的简单学习启发式方法在性能和泛化性方面超过了最先进的学习启发式方法，挑战了现有假设，并为组合优化的未来研究和创新开辟了新的方向。
Oct, 2023
本文提出了一种基于模拟退火的启发式搜索算法，在搜索空间上通过展开马尔可夫链到递归深度树来寻找最优解，利用连续表示的自旋状态和正则化项以及振荡子的动力学来探索选定的树节点周围的搜索空间，并在 NP - 困难问题（MAX-CUT）上验证了该算法与半定规划、模拟退火和相干 Ising 机的比较实验中能够在较少的迭代次数内获得更优解的优越性。
Mar, 2022