基于学习子句删除策略的SAT求解器分支策略

对于SAT求解器,目前流行的分支变量决策策略大多是基于冲突的变量活跃度评估算法,选择具有最大活性的未赋值变量作为决策变量,优先解决最近的冲突.但是,它们都忽略了包含决策变量的子句数目对布尔约束传播(BCP)的影响.针对此问题,提出了 一种基于学习子句删除策略的分支变量决策策略(VDALCD),在删除学习子句的同时减小被删除子句中变量的活跃度.基于VDALCD策略分别对Glucose4.1,MapleLCMDistChronoBT-DL-v2.1进行改进,形成了求解器Glucose4.1_VDALCD和Maple-DL_VDALCD.以2018年、2019年SAT国际竞赛题为基准测试例,将改进版本与原版本求解器进行比较.实验结果表明,在2018年的例子测试中,Gluose4.1_VDALCD比Gluose4.1多求出26个例子,增加了 15.5％.在2019年的例子测试中,Maple-DL_VDALCD 比 MapleLCMDistChronoBT-DL-v2.1 多求出 17个例子,增加了 7.6％.     

基于演绎长度的学习子句删除策略

学习子句删除策略是CDCL-SAT求解器中的一个重要内容,可以避免内存爆炸和加速单元传播。评估学习子句有用性的标准不同导致所删除的学习子句是不同的,极大地影响求解效率。基于CDCL算法的求解过程可被形式化为增加管理学习子句策略的归结演绎过程,基于此,提出一种基于演绎长度的学习子句评估方法,并与现有的基于文字块距离的评估方法结合,根据排序子句的基准不同,形成两种不同的结合算法。采用国际SAT竞赛的基准实例,与目前主流的求解器进行了实验对比分析。结果表明,所提的结合算法能更好地评估学习子句的有用性,较基于文字块距离策略的求解个数提高了4.1%,说明所提策略具有一定的优势。     

基于参与冲突分析次数的动态学习子句评估策略

针对现有学习子句评估策略的单一性,提出一种基于学习子句参与冲突分析次数的评估策略,并将该策略分别与经典的文字块距离评估策略和活跃值评估策略结合,形成两个动态学习子句评估策略。基于2018年SAT国际竞赛部分基准实例,将动态评估策略与原评估策略进行参数适应性对比实验,并通过2018和2017年的基准实例进行评估。结果表明动态评估策略能更好地评估学习子句的质量,由此生成的求解器在求解数量和速度方面表现出较好的求解性能。     

基于动态奖惩的分支策略的SAT完备算法

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题,提出了基于动态奖惩的分支策略。首先,对每次单子句传播的变元进行惩罚,依据变元是否产生冲突和产生冲突的间隔,确立不同的惩罚函数;其次,在学习阶段,利用学习子句确定对构造冲突有益的变元,非线性增加它们的活跃度;最后,选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上,完成了改进的动态奖惩算法——AP7。实验结果表明,相比glucose3.0算法,AP7算法的剪枝率提高了14.2%~29.3%,少数算例剪枝率的提高可达51%,且改进后的AP7算法相比glucose3.0算法,运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模,使搜索树更加平衡,减少计算时间。     

基于子句的动态检查强制文字的SAT求解器

检查强制文字是一种重要的预处理方法。结合学习子句,提出一种在求解过程中使用的策略—基于子句的动态检查强制文字(CNL),并且设计了一种易实现低成本的数据结构。分别实现了两个不同版本的求解器:Glucose_PRE和Glucose_CNL,前者在求解初始时将检查强制文字作为预处理,后者实现了基于子句的动态检查强制文字策略。实验测试结果表明,与Glucose_PRE和Glucose3.0求解器相比,求解器Glucose_CNL在求解2015年和2016年SAT竞赛的应用类型的实例时,求解实例个数更多,耗时更少,说明所提策略和所设计的数据结构均可提高求解器的求解性能。     

基于子句权重学习的求解SAT问题的遗传算法

该文提出了一种求解SAT问题的改进遗传算法（SAT—WAGA）．SAT-WAGA算法有多个改进性特点：将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散．该文最后描述了实现包括SAT—WAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议．实验结果表明：与一般遗传算法相比,SAT—WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善．     

基于SAT求解器的故障树最小割集求解算法

故障树分析广泛应用于核工业、航空航天和交通控制等安全攸关领域的安全性分析。求解故障树的最小割集是故障树分析的关键步骤。目前,对于大规模故障树的最小割集的求解方法主要是将故障树转化为二元决策图之后求解,其主要缺点在于算法在时间和空间上的消耗严重依赖良好的变量顺序。为了减少存储资源并加快求解速度,提出了一种基于可满足性问题的故障树最小割集求解算法。首先,将求解故障树最小割集问题转化为求解布尔可满足性问题。然后,利用可满足性问题求解器,通过迭代分析求得最小可满足解集合,即为对应故障树的最小割集。实验表明,本文算法求得的最小割集准确、有效并且在空间和时间上的消耗均要优于传统的基于二元决策图的故障树最小割集求解算法。     

基于趋势强度的SAT问题学习子句评估算法

针对命题逻辑公式求解过程中难以有效评估学习子句是否有利于后续搜索的问题,提出了一种基于学习子句趋势强度的评估算法。该算法首先通过分析学习子句在生存期内参与冲突分析的时间分布特征,将随机、离散的时间分布转换为连续的累积趋势强度;然后在删除周期达到时,通过设定趋势强度阈值删除在后续搜索过程中“不大可能”被使用的子句,保留“可能”被使用的子句;最后采用2015年、2016年SAT问题国际竞赛实例,将该算法与经典的活跃度评估算法和文字块距离(LBD)评估算法进行对比。实验结果表明,趋势强度评估算法在效率上明显优于活跃度评估算法,且求解的实例更多,同时与LBD算法基本持平。     

基于频次的SAT问题学习子句混合评估算法

为了有效管理学习子句,避免学习子句规模呈几何级增长,减少冗余学习子句对系统内存占用,从而提高布尔可满足性问题SAT求解器的求解效率,需要对学习子句进行评估,然后删减学习子句。传统的评估方式是基于学习子句的长度,保留较短的子句。当前主流的做法一个是变量衰减和VSIDS的子句评估方式,另外一个是基于文字块距离LBD的评估方式,也有将二者结合使用作为子句评估的依据。通过对学习子句参与冲突分析次数与问题求解的关系进行分析,将学习子句使用频率与LBD评估算法混合使用,既反映了学习子句在冲突分析中的作用,也充分利用了文字与决策层之间的信息。以Syrup求解器（GLUCOSE 4.1并行版本）为基准,在评估算法与并行子句共享策略方面做改进测试,通过实验对比发现,混合评估算法比LBD评估算法有优势,求解问题个数明显增多。     

Integrating advanced reasoning into a SAT solver

1 Introduction The SAT (Satisfiability) problem is one of the basic NP problems that have been widely researched. Many problems in EDA (Electronics Design Automation) domain such as ATPG (Automatic Test Pattern Generation), Logic Synthesis, Equivalence Checking[1] and Model Checking[2] can be reduced to the SAT problem. Typical algorithms for SAT can be classified into two categories: incomplete and complete ones. The former, including GSAT[3] and WalkSAT[4], are based on local…     

基于改进连续时间动态系统的模拟SAT求解器

针对布尔可满足性问题的高效求解进行了研究。首先,通过对k-SAT问题和基于耦合常微分方程形式的确定性连续时间动态系统的分析,提出了一种基于时延信息形式的改进连续时间动态系统方程,以保持集中搜索特性;然后,提出了实现该系统方程的三个主要组件即信号动态电路、辅助变量电路和数字验证电路的模拟设计。在信号动态电路的设计中,设计了一种获得更高性能、更小面积和更低功耗的模拟硬件形式;在提出的辅助变量电路和数字验证电路的模拟硬件设计中,实现了避免梯度下降搜索陷入无解和确定给定问题的解是否已经找到的目标;同时提出了降低面积和功耗的可替代辅助变量电路的两种设计方案。仿真实验结果表明,提出的新的模拟SAT求解器不仅是有效的,而且相比于单一软件算法实现的SAT求解器和其他硬件类SAT求解器具有更高的加速性能和更低的功耗。     

基于Partial MAX-SAT求解法的RBAC授权查询方法

为保证系统的安全性并体现授权的有效性,结合部分最大可满足性问题(Partial MAX-SAT)的研究,提出一种基于Partial MAX-SAT求解法的授权查询方法。使用转换规则将静态授权逻辑和动态互斥角色约束转化为严格子句,采用子句更新算法将满足不同匹配的请求权限转化为松弛子句,并利用子句编码及递归算法寻求真值指派,以满足所有严格子句和尽可能多的松弛子句。实验结果表明,该方法搜索的角色组合能够保证系统的安全性,并满足最小权限分配要求,且最大、精确匹配请求的查询效率优于MAX-SAT求解法。     

A parsimony tree for the SAT2002 competition

Twenty of the programs (solvers) submitted to the SAT 2002 Contest had no disqualifying errors. These solvers were run on 2023 satisfiability problems of varying hardnesses. Each solver was judged by which problems it could solve within the allowed time limit. Twelve solvers were best on some problem — they could solve it and the others could not. Only two solvers could not beat each remaining solver on some problems (where the problems could vary depending on which solver it was trying to beat). Thus, there is evidence that 18 solvers were extremely good. It is interesting to analyze the contest results in a way that groups together solvers with similar strengths and weaknesses. This paper uses the parsimony algorithm to produce a classification of the twenty solvers. The paper also has a second classification, almost the same as the first, for the twenty solvers, updated versions of two solvers, and a fictitious state of the art solver. The contest problems came in three groups, Industrial, Hand Made, and Random. The Random group of problems was about three times as large as the other two together. The classification identifies four groups of solvers (plus a miscellaneous group): weak solvers, incomplete solvers which are very good at some satisfiable Random problems, complete solvers which are very good at most Random problems, and complete solvers which are very good at Industrial and Hand Made problems.     

结合DOEC极小化策略的SAT求解极小碰集方法

在基于模型诊断中,诊断解通常是根据极小冲突集合簇进行相应的计算得到所有的极小碰集,所以提高极小碰集的求解效率是模型诊断的核心问题.因此提出结合基于元素覆盖集合度(degree of element coverage, DOEC)极小化策略的SAT求解极小碰集的方法SAT-MHS(satisfiability problem-minimal hitting sets).首先,方法SAT-MHS将碰集求解问题转换成SAT问题,即把所有的冲突集合以子句形式表示成SAT的输入CNF进行迭代求解.其次,提出比现有的基于子超集检测极小化策略(sub-superset detecting minimization, SSDM)更为高效的DOEC极小化策略进行极小化处理.由实验数据可见,与SSDM极小化策略相比,其优点是缩减了求解空间和迭代求解次数,尤其当求解规模较大问题时,其极小化效率越高.主要是因为其极小化不会随着待求解问题规模的增加而增加,而是只与冲突集合簇的大小相关,因此时间复杂度较低.实验结果表明,对于一些较大的实例,与目前效率最好的Boolean方法相比,SAT-MHS方法高效且易于实现,求解速度能提高10~20倍,DOEC极小化策略对比传统SSDM极小化策略能达到40倍左右.