Institute of Computing Technology, Chinese Academy IR
| 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
 |
| ISSN | 2095-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 |
| DOI | 10.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 |
| 引用统计 | |
| 文献类型 | 期刊论文 |
| 条目标识符 | 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. |
| 条目包含的文件 | 条目无相关文件。 | |||||
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论