Tailoring local search for partial MaxSAT

ISCAS OpenIR

	Tailoring local search for partial MaxSAT
	Cai, Shaowei (1); Luo, Chuan (3); Thornton, John (4); Su, Kaile (4); Cai, Shaowei
	2014
会议名称	28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014
页码	2623-2629
会议日期	July 27, 2014 - July 31, 2014
会议地点	Quebec City, QC, Canada
收录类别	EI
出版地	AI Access Foundation
ISBN	9781577356806
部门归属	(1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) Queensland Research Laboratory, NICTA, Brisbane, Australia; (3) Key Laboratory of High Confidence Software Technologies, Peking University, Beijing, China; (4) Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, Australia
摘要	Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called Dist. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that Dist significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, Dist dramatically outperforms previous local search algorithms and is comparable with complete algorithms.; Partial MaxSAT (PMS) is a generalization to SAT and MaxSAT. Many real world problems can be encoded into PMS in a more natural and compact way than SAT and MaxSAT. In this paper, we propose new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. We use these ideas to develop a local search PMS algorithm called Dist. Experimental results on PMS benchmarks from MaxSAT Evaluation 2013 show that Dist significantly outperforms state-of-the-art PMS algorithms, including both local search algorithms and complete ones, on random and crafted benchmarks. For the industrial benchmark, Dist dramatically outperforms previous local search algorithms and is comparable with complete algorithms.
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16611
专题	中国科学院软件研究所
通讯作者	Cai, Shaowei
推荐引用方式 GB/T 7714	Cai, Shaowei ,Luo, Chuan ,Thornton, John ,et al. Tailoring local search for partial MaxSAT[C]. AI Access Foundation,2014:2623-2629.