CSpace  > 中国科学院计算技术研究所期刊论文  > 英文
Empirical investigation of stochastic local search for maximum satisfiability
Chu, Yi1,2; Luo, Chuan1,3; Cai, Shaowei4; You, Haihang1
2019-02-01
发表期刊FRONTIERS OF COMPUTER SCIENCE
ISSN2095-2228
卷号13期号:1页码:86-98
摘要The maximum satisfiability (MAX-SAT) problem is an important NP-hard problem in theory, and has a broad range of applications in practice. Stochastic local search (SLS) is becoming an increasingly popular method for solving MAX-SAT. Recently, a powerful SLS algorithm called CCLS shows efficiency on solving random and crafted MAX-SAT instances. However, the performance of CCLS on solving industrial MAX-SAT instances lags far behind. In this paper, we focus on experimentally analyzing the performance of SLS algorithms for solving industrial MAX-SAT instances. First, we conduct experiments to analyze why CCLS performs poor on industrial instances. Then we propose a new strategy called additive BMS (Best from Multiple Selections) to ease the serious issue. By integrating CCLS and additive BMS, we develop a new SLS algorithm for MAX-SAT called CCABMS, and related experiments indicate the efficiency of CCABMS. Also, we experimentally analyze the effectiveness of initialization methods on SLS algorithms for MAX-SAT, and combine an effective initialization method with CCABMS, resulting in an enhanced algorithm. Experimental results show that our enhanced algorithm performs better than its state-of-the-art SLS competitors on a large number of industrial MAX-SAT instances.
关键词empirical investigation stochastic local search maximum satisfiability industrial instances additive BMS
DOI10.1007/s11704-018-7107-z
收录类别SCI
语种英语
资助项目National Key Research and Development Program of China[2016YFE0100300] ; National Key Research and Development Program of China[2017YFB02025] ; 100 Talents Program of the Chinese Academy of Sciences[2920154070] ; Knowledge Innovation Project of the Chinese Academy of Sciences[5120146040] ; Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing[2016A06] ; National Natural Science Foundation of China[61502464]
WOS研究方向Computer Science
WOS类目Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号WOS:000457525200007
出版者HIGHER EDUCATION PRESS
引用统计
被引频次:5[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://119.78.100.204/handle/2XEOYT63/3445
专题中国科学院计算技术研究所期刊论文_英文
通讯作者You, Haihang
作者单位1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100190, Peoples R China
2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
3.State Key Lab Math Engn & Adv Comp, Wuxi 214125, Peoples R China
4.Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714
Chu, Yi,Luo, Chuan,Cai, Shaowei,et al. Empirical investigation of stochastic local search for maximum satisfiability[J]. FRONTIERS OF COMPUTER SCIENCE,2019,13(1):86-98.
APA Chu, Yi,Luo, Chuan,Cai, Shaowei,&You, Haihang.(2019).Empirical investigation of stochastic local search for maximum satisfiability.FRONTIERS OF COMPUTER SCIENCE,13(1),86-98.
MLA Chu, Yi,et al."Empirical investigation of stochastic local search for maximum satisfiability".FRONTIERS OF COMPUTER SCIENCE 13.1(2019):86-98.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Chu, Yi]的文章
[Luo, Chuan]的文章
[Cai, Shaowei]的文章
百度学术
百度学术中相似的文章
[Chu, Yi]的文章
[Luo, Chuan]的文章
[Cai, Shaowei]的文章
必应学术
必应学术中相似的文章
[Chu, Yi]的文章
[Luo, Chuan]的文章
[Cai, Shaowei]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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