不完整 MaxSAT 的近似策略
本文提出了一种新的框架 UpMax,将分割过程与 MaxSAT 解决算法分离,使用户能够根据问题来提出分割方案,证明分割对于基于不可满足性的 MaxSAT 算法的性能有很大的影响。
May, 2023
本研究使用 MaxSAT 问题中的 SPB 约束和子句权重技术,提出了一种新的局部搜索算法 SPB-MaxSAT,为 MaxSAT 局部搜索求解器的子句权重方法提供了新的视角和优秀的性能。
Jan, 2024
本文提出了一种将搜索方法与半定规划方法相结合的算法,其用于解决 MAX2SAT 问题。文中称,使用这种方法能够显著提高问题的解决速度,并在一些问题上取得了 order of magnitude 级别的速度提升。
Dec, 2018
该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT,用于解决不同类型的布尔可满足性问题,包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数,构建了统一的整数规划表示方法,并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构,在 SAT 问题上应用了蒙特卡罗树搜索(MCTS)方法,证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明,该方法能够剪枝不必要的搜索空间,找到问题的最优布尔赋值,同时为 SAT 问题的监督学习方法提供多样的标签。
Dec, 2023
本研究分析了现有的基于不可满足子公式识别的最大可满足性问题(MaxSAT)算法,并提出了几个关键性优化和新的替代算法,这些优化和新算法在实际应用中的 MaxSAT 实例上提供了显着的性能提升。
Dec, 2007
本文研究了加权最大可满足性问题中检索骨干的计算复杂度,并提出了一种基于骨干的局部搜索算法,称为 BGLS。实验结果表明,在质量和运行时间方面,BGLS 比现有算法表现更优异。
Apr, 2017
本文提出了一种基于多臂赌博机的本地搜索算法 BandHS 用来解决 MaxSAT 及其两个泛化问题,和一个初始化方法优化算法的表现。经过大量实验证明,本文提出的方法在解决 MaxSAT 问题时表现出色。
Nov, 2022
本文介绍了一种新的方法,使用黑箱预言机,通过 NP-Oracle 实际求解带权重赋值的模型计数问题和分布感知的满足分配的抽样问题,从而在中等规模的问题上获得了强大的理论保证。
Apr, 2014
本文提出了加权布尔优化(Weighted Boolean Optimization,WBO)的新统一框架,并提出了一种基于不可满足性的算法为 WBO 提供解决方案,并且该算法可用于解决众多相关问题,包括 非常规的伪布尔约束条件。实验结果表明,基于不可满足性的算法比现有的专用算法更有效。
Mar, 2009