求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

求解SAT问题的退火遗传算法

提出一种将遗传算法与模拟退火算法相结合的SAT问题求解算法SAT-SAGA.该算法以遗传算法流程为主体,并把模拟退火机制融入其中,用以调整优化群体,防止陷入局部最优和出现早熟;在进化过程中算法采用了最优染色体保存策略,防止进化过程的发散.实验表明:该算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.     

Solving the resolution-free SAT problem by submodel propagation in linear time

We present a method, called Unicorn-SAT, based on submodel propagation, which solves the resolution-free SAT problem in linear time. A formula is resolution-free if there are no two clauses which differ only in one variable, i.e., each clause is blocked for each literal in it. A resolution-free formula is satisfiable or it contains the empty clause. For such a restricted formula we can find a model in linear time by submodel propagation. Submodel propagation is hyper-unit propagation by a submodel generated from a minimal clause. Hyper-unit propagation is unit propagation simultaneously by literals, as unit clauses, of a partial assignment. We obtain a submodel, i.e., a part of the model, by negation of a neighbor-resolution-mate of a minimal clause, which is a clause with the smallest number of literals in the formula. We obtain a neighbor-resolution-mate of a clause by negating one literal in it. By submodel propagation we obtain a formula which has fewer variables and clauses and remains resolution-free. Therefore, we can obtain a model by joining the submodels while we perform submodel propagation recursively until the formula becomes empty.Sponsored by Upper Austrian Government (Ph.D. scholarship) and SFB/FWF project P1302.     

Solving the resolution-free SAT problem by submodel propagation in linear time

We present a method, called Unicorn-SAT, based on submodel propagation, which solves the resolution-free SAT problem in linear time. A formula is resolution-free if there are no two clauses which differ only in one variable, i.e., each clause is blocked for each literal in it. A resolution-free formula is satisfiable or it contains the empty clause. For such a restricted formula we can find a model in linear time by submodel propagation. Submodel propagation is hyper-unit propagation by a submodel generated from a minimal clause. Hyper-unit propagation is unit propagation simultaneously by literals, as unit clauses, of a partial assignment. We obtain a submodel, i.e., a part of the model, by negation of a neighbor-resolution-mate of a minimal clause, which is a clause with the smallest number of literals in the formula. We obtain a neighbor-resolution-mate of a clause by negating one literal in it. By submodel propagation we obtain a formula which has fewer variables and clauses and remains resolution-free. Therefore, we can obtain a model by joining the submodels while we perform submodel propagation recursively until the formula becomes empty.     

Formal verification of a modern SAT solver by shallow embedding into Isabelle/HOL

We present a formalization and a formal total correctness proof of a MiniSAT-like SAT solver within the system Isabelle/HOL. The solver is based on the DPLL procedure and employs most state-of-the-art SAT solving techniques, including the conflict-guided backjumping, clause learning, and the two-watched unit propagation scheme. A shallow embedding into Isabelle/HOL is used and the solver is expressed as a set of recursive HOL functions. Based on this specification, the Isabelle’s built-in code generator can be used to generate executable code in several supported functional languages (Haskell, SML, and OCaml). The SAT solver implemented in this way is, to our knowledge, the first fully formally and mechanically verified modern SAT solver.     

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

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

基于动态奖惩的CDCL SAT求解器分支启发式算法

分支启发式算法在CDCL SAT求解器中有着非常重要的作用,传统的分支启发式算法在计算变量活性得分时只考虑了冲突次数而并未考虑决策层和冲突决策层所带来的影响。为了提高SAT问题的求解效率,受EVSIDS和ACIDS的启发,提出了基于动态奖惩DRPB的分支启发式算法。每当冲突发生时,DRPB通过综合考虑冲突次数、决策层、冲突决策层和变量冲突频率来更新变量活性得分。用DRPB替代VSIDS算法改进了Glucose 3.0,并测试了SATLIB基准库、2015年和2016年SAT竞赛中的实例。实验结果表明,与传统、单一的奖励变量分支策略相比,所提分支策略可以通过减少搜索树的分支和布尔约束传播次数来减小搜索树的规模并提高SAT求解器的性能。     

Visualizing SAT Instances and Runs of the DPLL Algorithm

SAT-solvers have turned into essential tools in many areas of applied logic like, for example, hardware verification or satisfiability checking modulo theories. However, although recent implementations are able to solve problems with hundreds of thousands of variables and millions of clauses, much smaller instances remain unsolved. What makes a particular instance hard or easy is at most partially understood – and is often attributed to the instance’s internal structure. By converting SAT instances into graphs and applying established graph layout techniques, this internal structure can be visualized and thus serve as the basis of subsequent analysis. Moreover, by providing tools that animate the structure during the run of a SAT algorithm, dynamic changes of the problem instance become observable. Thus, we expect both to gain new insights into the hardness of the SAT problem and to help in teaching SAT algorithms.     

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

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

Solving SAT by Algorithm Transform of Wu s Method

Recently algorithms for solving propositional satisfiability problem, or SAT,have aroused great interest,and more attention has been paid to transformation problem solving.The commonly used transformation is representation transform,but since its intermediate computing procedure is a black box from the viewpoint of the original problem,this approach has many limitations.In this paper,a new approach called algorithm transform is proposed and applied to solving SAT by Wu‘s method,a general algorithm for solving polynomial equations.B y establishing the correspondence between the primitive operation in Wu‘s method and clause resolution is SAT,it is shown that Wu‘s method,when used for solving SAT,,is primarily a restricted clause resolution procedure.While Wu‘s method introduces entirely new concepts.e.g.characteristic set of clauses,to resolution procedure,the complexity result of resolution procedure suggests an exponential lower bound to Wu‘s method for solving general polynomial equations.Moreover,this algorithm transform can help achieve a more efficient implementation of Wu‘s method since it can avoid the complex manipulation of polynomials and can make the best use of domain specific knowledge.     

Survey Propagation：一种求解SAT的高效算法

Survey propagation是一种新生的SAT(CSP)算法。它基于统计物理的spin glass模型，针对具体问题进行纵览(survey)，从而极大地降低求解的复杂度。但sp算法在某些时候不收敛，或引导向错误的解。对此，G．Parisi提出一种复杂回溯(backtrack)算法，而作者在sp中加入简单回溯，也使一部分此类问题得到解决。     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

基于演化算法的SAT问题求解

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.     

规划问题编码成SAT问题研究

智能规划问题是一个NP-hard的问题。近年来,由于在可满足问题（SAT）研究领域取得了较大进展,出现了一大批快速的能达到工业级应用的SAT solver求解器的出现,这使得运用可满足技术来求解规划问题的方法越来越得到智能规划研究者们的重视。用可满足技术求解规划问题的首要任务是必须将规划问题“翻译”成可满足问题。讨论了如何将规划问题编码成命题可满足问题的一般技术,并对“直接编码”和“基于规划图的编码”两种编码技术进行了比较,指出了两种编码技术各自的优缺点。在此基础上,深入地分析了各种不同的编码方案之间的异同点以及它们各自的优缺点。最后,指出了用SAT技术求解规划问题中存在的一些问题以及相关改进方法。     

求解SAT问题的算法的研究进展

SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望。     

基于几何规划的布尔可满足问题求解方法

布尔可满足问题是计算机科学中诸多领域的重要问题,它的快速求解具有十分重要的意义.将具有实际物理背景的Solar算法中的拟物算法与几何规划相结合,提出并实现了一种布尔可满足性问题的连续求解方法.经实验验证,这种算法对布尔可满足性问题的求解具有一定的实用价值.     

基于寻找可满足2SAT子问题的SAT算法*

可满足问题（SAT）是一个NP-Hard问题。提出了一种求解SAT的新算法（FFSAT）。该算法将SAT问题转换为寻找一个可满足的2-SAT子问题。SAT问题虽然是NP完全问题,但是当所有子句长度不大于2时,SAT问题可以在线性时间求解。使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题。实验结果表明,采用本算法的结果优于UnitWalk。     

求解旅行商问题的混合粒子群优化算法

结合遗传算法、蚁群算法和模拟退火算法的思想，提出用混合粒子群算法来求解著名的旅行商问题．与模拟退火算法、标准遗传算法进行比较，24种混合粒子群算法的效果都比较好，其中交叉策略D和变异策略F的混合粒子群算法的效果最好，而且简单有效．对于目前仍没有较好解法的组合优化问题，通过此算法修改很容易解决．     

作业车间调度问题的布谷鸟搜索算法求解

布谷鸟搜索算法是一种新型元启发式优化算法,该算法受到自然界中布谷鸟的巢寄生行为启发而提出。首先分析了布谷鸟搜索算法的仿生原理和数学描述,采用基于工序的编码方式对最小化最大完工时间的作业车间调度问题进行布谷鸟搜索算法求解。通过典型算例进行仿真实验,测试结果表明布谷鸟搜索算法求解作业车间调度问题的可行性和有效性,优于萤火虫算法和基本粒子群算法,是解决生产调度问题的一种有效方法。