QQ客服 官方微博 反馈留言

	CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability
	Cai, Shaowei ; Luo, Chuan ; Su, Kaile
	2015
英文摘要	This paper presents a stochastic local search (SLS) solver for SAT named CCAnr, which is based on the configuration checking strategy and has good performance on non-random SAT instances. CCAnr switches between two modes: it flips a variable according to the CCA (configuration checking with aspiration) heuristic if any; otherwise, it flips a variable in a random unsatisfied clause (which we refer to as the focused local search mode). The main novelty of CCAnr lies on the greedy heuristic in the focused local search mode, which contributes significantly to its good performance on structured instances. Previous two-mode SLS algorithms usually utilize diversifying heuristics such as age or randomized strategies to pick a variable from the unsatisfied clause. Our experiments on combinatorial and application benchmarks from SAT Competition 2014 show that CCAnr has better performance than other state-of-the-art SLS solvers on structured instances, and its performance can be further improved by using a preprocessor CP3. Our results suggest that a greedy heuristic in the focused local search mode might be helpful to improve SLS solvers for solving structured SAT instances.; EI; CPCI-S(ISTP); shaoweicai.cs@gmail.com; chuanluosaber@gmail.com; k.su@griffith.edu.au; 1-8; 9340
语种	英语
出处	THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2015
DOI标识	10.1007/978-3-319-24318-4_1
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/436885]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Cai, Shaowei,Luo, Chuan,Su, Kaile. CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability. 2015-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。