[PDF][PDF] Read-once resolution for unsatisfiability-based Max-SAT algorithms

F Heras, J Marques-Silva - IJCAI, 2011 - Citeseer
IJCAI, 2011Citeseer
This paper proposes the integration of the resolution rule for Max-SAT with unsatisfiability-
based Max-SAT solvers. First, we show that the resolution rule for Max-SAT can be safely
applied as dictated by the resolution proof associated with an unsatisfiable core when such
proof is read-once, that is, each clause is used at most once in the resolution process.
Second, we study how this property can be integrated in an unsatisfiability-based solver. In
particular, the resolution rule for Max-SAT is applied to read-once proofs or to read-once …
Abstract
This paper proposes the integration of the resolution rule for Max-SAT with unsatisfiability-based Max-SAT solvers. First, we show that the resolution rule for Max-SAT can be safely applied as dictated by the resolution proof associated with an unsatisfiable core when such proof is read-once, that is, each clause is used at most once in the resolution process. Second, we study how this property can be integrated in an unsatisfiability-based solver. In particular, the resolution rule for Max-SAT is applied to read-once proofs or to read-once subparts of a general proof. Finally, we perform an empirical investigation on structured instances from recent Max-SAT evaluations. Preliminary results show that the use of read-once resolution substantially improves the performance of the solver.
Citeseer
以上显示的是最相近的搜索结果。 查看全部搜索结果