利用远见概率采样提升本地搜索 MaxSAT 求解器的通用策略
本文提出了一种基于多臂赌博机的本地搜索算法 BandHS 用来解决 MaxSAT 及其两个泛化问题,和一个初始化方法优化算法的表现。经过大量实验证明,本文提出的方法在解决 MaxSAT 问题时表现出色。
Nov, 2022
本研究提出了一个名为 BandMaxSAT 的局部搜索算法,它应用多臂赌博机模型来引导搜索方向,特别适用于 Partial MaxSAT (PMS) 和 Weighted PMS (WPMS) 问题,相较于现有算法 SATLike3.0,实验证明 BandMaxSAT 在解决这些问题上更为优秀,与 TT-Open-WBO-Inc 结合可以获得更好的效果。
Jan, 2022
本研究使用 MaxSAT 问题中的 SPB 约束和子句权重技术,提出了一种新的局部搜索算法 SPB-MaxSAT,为 MaxSAT 局部搜索求解器的子句权重方法提供了新的视角和优秀的性能。
Jan, 2024
该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT,用于解决不同类型的布尔可满足性问题,包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数,构建了统一的整数规划表示方法,并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构,在 SAT 问题上应用了蒙特卡罗树搜索(MCTS)方法,证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明,该方法能够剪枝不必要的搜索空间,找到问题的最优布尔赋值,同时为 SAT 问题的监督学习方法提供多样的标签。
Dec, 2023
本文介绍了一种结合 solution prediction model 和神经网络的方法 ——NLocalSAT,用于提高 stochastic local search 在解 Boolean satisfiability problem 时的有效性,并且在 SAT Competition 2018 的实验中取得了 27% ~ 62% 的性能提升。
Jan, 2020
通过代数决策图和级联项目 - 加入树生成器,我们提出了动态规划最大可满足性(DPMS),一种解决广义 MaxSAT 问题的新方法。实证结果表明,DPMS 能够快速解决某些问题,由此开辟了未来更多研究的新方向。
May, 2022
提出了基于梯度驱动连续局部搜索(CLS)的高度并行混合 SAT 求解器 FastFourierSAT,该算法利用图形处理单元(GPU)的并行性能加速计算,可以比之前的方法快 100 + 倍,并在更大规模的案例上表现出良好的性能。
Aug, 2023
该研究论文介绍了一种使用候选父集进行并行采样的近似算法,可以被视为高维数据结构学习的现有算法(MINOBS)的扩展,命名为并行采样 MINOBS (PS-MINOBS)。实验结果表明,与有运行时间限制的 MINOBS 相比,该算法在大多数情况下发现了更高分数的结构。
Feb, 2022
本文通过分析顺序版本算法的运行时行为,提出了一种评估给定算法并行性能的框架,并将此方法应用于研究两种 SAT 局部搜索求解器的并行性能,结果表明模型能够准确预测性能并展示了不同情况下局部搜索求解器的运行时分布。
Jan, 2024