论文标题
关于伪树树约束学习中无关的文字
On Irrelevant Literals in Pseudo-Boolean Constraint Learning
论文作者
论文摘要
在利用基于切割平面的推理的PB求解器中学习伪树状（PB）的约束并不像冲突驱动的子句学习求解器中的从句学习那样充分理解。在本文中，我们表明，使用切割平面得出的Pb约束可能包含\ emph {Inlreclevant Mliterals}，即，其分配的值（无论它们是什么）永远不会改变约束的真实价值。这样的文字可能会导致推断的约束，这些限制比应有的薄弱，从而影响求解器构建的证据的大小，从而影响其性能。这表明，应重新考虑基于切割平面的PB求解器的当前实施，以防止产生无关紧要的文字。实际上，检测和删除无关的文字在实践中太昂贵，无法被视为一种选择（相关的问题是NP-HARD。
Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cutting planes based inference is not as well understood as clause learning in conflict-driven clause learning solvers. In this paper, we show that PB constraints derived using cutting planes may contain \emph{irrelevant literals}, i.e., literals whose assigned values (whatever they are) never change the truth value of the constraint. Such literals may lead to infer constraints that are weaker than they should be, impacting the size of the proof built by the solver, and thus also affecting its performance. This suggests that current implementations of PB solvers based on cutting planes should be reconsidered to prevent the generation of irrelevant literals. Indeed, detecting and removing irrelevant literals is too expensive in practice to be considered as an option (the associated problem is NP-hard.
