A SAT-Based Approach to MinSAT

被引：8

作者：

Ansotegui, Carlos ^{[1
]}

Li, Chu Min ^{[2
]}

Manya, Felip ^{[3
]}

Zhu, Zhu ^{[2
]}

机构：

[1] Univ Lleida, Lleida, Spain

[2] Univ Picardie Jules Verne, MIS, Amiens, France

[3] CSIC, Artificial Intelligence Res Inst IIIA, Bellaterra, Spain

来源：

ARTIFICIAL INTELLIGENCE RESEARCH AND DEVELOPMENT | 2012年 / 248卷

关键词：

Boolean Optimization; MinSAT; MaxSAT;

D O I：

10.3233/978-1-61499-139-7-185

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A Partial MinSAT instance is a set of clauses where each clause is declared to be either hard or soft, and the Partial MinSAT problem consists in finding an assignment that satisfies all the hard clauses, and minimizes the number of satisfied soft clauses. In this paper we present an algorithm for solving Partial MinSAT that relies on solving a sequence of SAT instances, and report on an empirical investigation that provides evidence that our approach solves crafted and industrial instances that are beyond the reach of existing approaches to Partial MinSAT.

引用

页码：185 / +

页数：2

共 12 条

[1] Ansótegui C, 2009, LECT NOTES COMPUT SC, V5584, P427, DOI 10.1007/978-3-642-02777-2_39
[2] DAVIES J, 2011, CP, V6876, P225
[3] Solving satisfiability problems with preferences
Di Rosa, Emanuele
Giunchiglia, Enrico
Maratea, Marco
[J]. CONSTRAINTS, 2010, 15 (04) : 485 - 515
[4] Heras F., 2011, AAAI
[5] Kugel A., 2012, P LEARN INT OPT C LI
[6] Kugel A., 2010, P WORKSH PRAGM SAT
[7] Li CM, 2007, J ARTIF INTELL RES, V30, P321
[8] Li CM, 2010, LECT NOTES COMPUT SC, V6175, P363
[9] MaxSAT, hard and soft constraints
[J]. Front. Artif. Intell. Appl., 2009, 1 (613-631): : 613 - 631
[10] Li Chu Min, 2012, ARTIFICIAL INTELLIGE

← 1 2 →