现代求解器在求解SAT问题高效，在解决工业问题转化的cnf级别的样例显示出惊人的能力。CDCL框架的提出被证明是现代求解器中最主流的解决方案，包括若干模块。其中学习子句的管理是最最为核心的部件，涉及到。The global ideaof clause learning is that during the unit propagation process, when a current branch of the search tree leads to a conflict, moderns SAT solvers learn a conflict clause that helps unit propagation to discover one of the implications missed at an earlier level. 以至于整个求解器可以看做是一个学习子句生成器【】。

主要内容

we propose a novel approach to identify the most relevant learned clauses without favoring or excluding any of the proposed measures, but by adopting the notion of dominance relationship among those measures. Our approach bypasses the problem of the diversity of results and reaches a compromise between the assessments of these measures. Furthermore, the proposed approach also avoids another non-trivial problem which is the amount of clauses to be deleted at each reduction of the learned clause database.

译文：我们提出了一种新颖的方法来识别最相关的已学习的条款，而不支持或排除任何建议的措施，而是采用这些措施之间的支配关系的概念。我们的方法绕过了结果的多样性问题，并在对这些措施的评估之间达成妥协。

一、对学习子句管理的认识（表述的非常精炼）

　　Managing the learned clauses database was the subject of several studies [17, 19, 11, 2, 3, 14]. These strategies were proposed with the objective to maintain a learned clause database of reasonable size by eliminating clauses deemed irrelevant to the subsequent search. The general principle of these strategies is that, at each conflict, an activity is associated to the learned clauses (static strategy). Such heuristic-based activity aims to weight each clause according to its relevance to the search process. In the case of dynamic strategies, such clauses activities are dynamically updated. The reduction of the learned clauses database consists in eliminating inactive or irrelevant clauses. Although all the learned clause deletion strategies proposed in the literature are shown to be empirically efficient, identifying the most relevant clause to maintain during the search process remains a challenging task.

　　Our motivation in this work comes from the observation that the use of different relevant-based deletion strategies gives different performances.译文：我们的动机来自于观察到使用不同的基于关联的删除策略会产生不同的表现。Our goal is to take advantage of several relevant learned clauses deletion strategies by seeking a compromise between them through a dominance relationship.译文：我们的目标是利用几个相关的学习子句删除策略，通过优势关系寻求它们之间的妥协。

　　该文献提出了以下一些新名词：

      　　 轮廓查询、支配模式、非主导关联规则

       　　天际线的概念——用于数据库管理和数据挖掘的概念。首次应用于SAT求解器的学习子句管理。

　　　　一些有效的基于关联的学习子句删除策略。

　　　　基于支配关系的子句删除策略。

二、On the learned clauses database management strategies学习子句集管理策略

　　1.译文：Minisat[11]认为，在最近的冲突分析中涉及最多的条款是相关的，并删除了在最近的冲突分析中很少涉及的已学习的条款。

　　2.LBD

　　Another strategy called LBD for Literal Block Distance was proposed in [2]. LBD based measure is also exploited by most of the best state-of-the-art SAT solver (Glucose, Lingeling [6]) and whose efficiency has been proved empirically. LBD based measure uses the number of different levels involved in a given learned clause to quantify the quality of the learned clauses. Hence, the clauses with smaller LBD are considered as more relevant.

　　3.学习子句的动态冻结和激活

　　In [3], a new dynamic management policy of the learned clauses database is proposed. It is based on a dynamic freezing and activation principle of the learned clauses.译文：在[3]中，提出了一种新的学习子句数据库动态管理策略。它是基于学习子句的动态冻结和激活原理。

　　At a given search state, using a relevant selection function based on progress saving (PSM), it activates the most promising learned clauses while freezing irrelevant ones.译文：在给定的搜索状态下，使用基于进度保存(PSM)的相关选择函数，它会激活最有希望学习的子句，而冻结不相关的子句。

　　4.回溯水平的BTL

　　In [14], a new criterion to quantify the relevance of a clause using its backtrack level called BTL for BackTrack Level was proposed.译文：提出了一种使用回溯水平量化条款相关性的新标准，即回溯水平的BTL。 From experiments, the authors observed that the learned clauses with small BTL values are used more often in the unit propagation process than those with higher BTL values. 译文：通过实验发现，BTL值较小的学习子句比BTL值较高的子句在单位传播过程中使用得更多。More precisely, the authors observed that the learned clauses with BTL value less than 3 are always used much more than the remaining clauses. Starting from this observation, and motivated by the fact that a learned clause with smaller BTL contains more literals from the top of the search tree, the authors deduce that relevant clauses are those allowing a higher backtracking in the search tree (having small BTL value).译文：更准确地说，作者观察到BTL值小于3的已学习的子句的使用频率总是比其他子句的使用频率高得多。从这个观察开始，并基于这样一个事实，即具有较小BTL的学习子句包含来自搜索树顶部的更多文字，作者推断出相关子句是那些允许在搜索树中进行更高的回溯的子句(具有较小的BTL值)。

　　5.最近在[15,1]中提出了几个其他的learned子句数据库策略。（1）大小有界学习策略；（2）保留一部分随机性；

　　译文：从[15]中获得的成绩来看，作者表明15年前提出的大小有界学习策略[19,4,5]并没有结束，仍然是预测已学习从句质量的好方法。

　　译文：他们表明，在大小有界学习中加入随机性是一种很好的实现控制多样化的方法，允许支持短的子句，同时保持大子句的一小部分，以获得了一些解决证明SAT实例。

　　6.

　　译文：本研究开启了许多关于learned clauses数据库策略的讨论，并对目前最先进的其他策略所宣称的有效性提出了质疑[11,2]。

　　In [1] the authors use the community structure of industrial SAT instances to identify a set of highly useful learned clauses.译文：在[1]中，作者使用工业SAT实例的社区结构来识别一组非常有用的学习子句。 They show that augmenting a SAT instance with the clauses learned by the solver during its execution does not always mean to make the instance easy. 译文：它们表明，用求解器在执行过程中学习到的子句来扩充一个SAT实例并不总是意味着使实例变得容易。However, the authors show that augmenting the formula with a set of clauses based on the community structure of the formula improves the performance of the solver in many cases. 译文：在许多情况下，根据公式的社区结构用一组子句来扩充公式可以提高求解器的性能。The different performances obtained by each strategy suggests that the question on how to predict efficiently the ”best” learned clauses is still open and deserves further investigation.译文：每种策略的不同表现表明，如何有效地预测“最佳”习得的子句仍然是一个有待进一步研究的问题。

　　7.讨论删除学习子句的操作频率和删除规模大小

　　On the other hand, it is important to note that the efficiency of most of these state-of-the-art learned clauses management strategies heavily depends on the cleaning frequency and on the amount of clauses to be deleted each time. 译文：大多数这些新的学习子句管理策略的效率很大程度上取决于清洗频率和每次删除的条款的数量。

　　（1）.删除一半。Generally, all the CDCL SAT solvers using these strategies exactly delete half of the learned clauses at each learned clauses database reduction step. For example, the CDCL SAT solver Minisat [11] and Glucose [2] delete half of the learned clauses at each cleaning.

　　（2）删除的数量是动态调整的，与参考学习子句数量相关。Therefore, the efficiency of this amount of learned clauses to delete (e.g the half) at each cleaning step of the learned clauses database has not been demonstrated theoretically, but instead experimentally. For our knowledge, there are not many studies in the literature on how to determine the amount of clauses to be deleted each time. 译文：据我们所知，文献中关于如何确定每次删除的子句数量的研究并不多。This paper proposes an approach to identify the relevant learned clauses during the resolution process without favoring any of the best reported relevant measures and which frees itself of the amount of clauses to be removed at each time: the amount of learned clauses to delete corresponds at each time to the number of learned clauses dominated by one particular learned clause of the set of the current learned clauses which is called in the following sections, the reference learned clause。译文：本文提出了一种在解析过程中识别相关习得子句的方法，不偏袒任何最好的报道相关措施，并且使其每次都不需要删除大量子句。译文：每次要删除的学习子句的数量对应于当前学习子句集合中一个特定的学习子句所占的学习子句的数量，这个学习子句在下面的章节中被称为参考学习子句。

学习子句管理——文献学习Towards Learned Clauses Database Reduction Strategies Based on Dominance Relationship