Branching Strategy Selection Approach Based on Vivification Ratio |
| |
Authors: | Mao Luo Chumin Li Xinyun Wu Shuolin Li Zhipeng Lv |
| |
Affiliation: | School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China;School of Computer Science, Huazhong University of Science and Technology, Wuhan 430074, China; MIS, University of Picardie Jules Verne, Amiens CS 52501, France; Aix Marseille Univ., University of Toulon, CNRS, LIS, Marseille CS 60584, France;School of Computer Science, Hubei University of Technology, Wuhan 430068, China |
| |
Abstract: | The two most effective branching strategies LRB and VSIDS perform differently on different types of instances. Generally, LRB is more effective on crafted instances, while VSIDS is more effective on application ones. However, distinguishing the types of instances is difficult. To overcome this drawback, we propose a branching strategy selection approach based on the vivification ratio. This approach uses the LRB branching strategy more to solve the instances with a very low vivification ratio. We tested the instances from the main track of SAT competitions in recent years. The results show that the proposed approach is robust and it significantly increases the number of solved instances. It is worth mentioning that, with the help of our approach, the solver Maple_CM can solve additional 16 instances for the benchmark from the 2020 SAT competition. |
| |
Keywords: | satisfiability conflict-driven clause learning branching heuristics clause vivification |
|
| 点击此处可从《》浏览原始摘要信息 |
|
点击此处可从《》下载全文 |
|